Lots of documentation fixes, and minor tweaks.
[jonesforth.git] / jonesforth.S
1 /*      A sometimes minimal FORTH compiler and tutorial for Linux / i386 systems. -*- asm -*-
2         By Richard W.M. Jones <rich@annexia.org> http://annexia.org/forth
3         This is PUBLIC DOMAIN (see public domain release statement below).
4         $Id: jonesforth.S,v 1.17 2007-09-08 22:10:43 rich Exp $
5
6         gcc -m32 -nostdlib -static -Wl,-Ttext,0 -o jonesforth jonesforth.S
7
8         INTRODUCTION ----------------------------------------------------------------------
9
10         FORTH is one of those alien languages which most working programmers regard in the same
11         way as Haskell, LISP, and so on.  Something so strange that they'd rather any thoughts
12         of it just go away so they can get on with writing this paying code.  But that's wrong
13         and if you care at all about programming then you should at least understand all these
14         languages, even if you will never use them.
15
16         LISP is the ultimate high-level language, and features from LISP are being added every
17         decade to the more common languages.  But FORTH is in some ways the ultimate in low level
18         programming.  Out of the box it lacks features like dynamic memory management and even
19         strings.  In fact, at its primitive level it lacks even basic concepts like IF-statements
20         and loops.
21
22         Why then would you want to learn FORTH?  There are several very good reasons.  First
23         and foremost, FORTH is minimal.  You really can write a complete FORTH in, say, 2000
24         lines of code.  I don't just mean a FORTH program, I mean a complete FORTH operating
25         system, environment and language.  You could boot such a FORTH on a bare PC and it would
26         come up with a prompt where you could start doing useful work.  The FORTH you have here
27         isn't minimal and uses a Linux process as its 'base PC' (both for the purposes of making
28         it a good tutorial). It's possible to completely understand the system.  Who can say they
29         completely understand how Linux works, or gcc?
30
31         Secondly FORTH has a peculiar bootstrapping property.  By that I mean that after writing
32         a little bit of assembly to talk to the hardware and implement a few primitives, all the
33         rest of the language and compiler is written in FORTH itself.  Remember I said before
34         that FORTH lacked IF-statements and loops?  Well of course it doesn't really because
35         such a lanuage would be useless, but my point was rather that IF-statements and loops are
36         written in FORTH itself.
37
38         Now of course this is common in other languages as well, and in those languages we call
39         them 'libraries'.  For example in C, 'printf' is a library function written in C.  But
40         in FORTH this goes way beyond mere libraries.  Can you imagine writing C's 'if' in C?
41         And that brings me to my third reason: If you can write 'if' in FORTH, then why restrict
42         yourself to the usual if/while/for/switch constructs?  You want a construct that iterates
43         over every other element in a list of numbers?  You can add it to the language.  What
44         about an operator which pulls in variables directly from a configuration file and makes
45         them available as FORTH variables?  Or how about adding Makefile-like dependencies to
46         the language?  No problem in FORTH.  This concept isn't common in programming languages,
47         but it has a name (in fact two names): "macros" (by which I mean LISP-style macros, not
48         the lame C preprocessor) and "domain specific languages" (DSLs).
49
50         This tutorial isn't about learning FORTH as the language.  I'll point you to some references
51         you should read if you're not familiar with using FORTH.  This tutorial is about how to
52         write FORTH.  In fact, until you understand how FORTH is written, you'll have only a very
53         superficial understanding of how to use it.
54
55         So if you're not familiar with FORTH or want to refresh your memory here are some online
56         references to read:
57
58         http://en.wikipedia.org/wiki/Forth_%28programming_language%29
59
60         http://galileo.phys.virginia.edu/classes/551.jvn.fall01/primer.htm
61
62         http://wiki.laptop.org/go/Forth_Lessons
63
64         Here is another "Why FORTH?" essay: http://www.jwdt.com/~paysan/why-forth.html
65
66         ACKNOWLEDGEMENTS ----------------------------------------------------------------------
67
68         This code draws heavily on the design of LINA FORTH (http://home.hccnet.nl/a.w.m.van.der.horst/lina.html)
69         by Albert van der Horst.  Any similarities in the code are probably not accidental.
70
71         Also I used this document (http://ftp.funet.fi/pub/doc/IOCCC/1992/buzzard.2.design) which really
72         defies easy explanation.
73
74         PUBLIC DOMAIN ----------------------------------------------------------------------
75
76         I, the copyright holder of this work, hereby release it into the public domain. This applies worldwide.
77
78         In case this is not legally possible, I grant any entity the right to use this work for any purpose,
79         without any conditions, unless such conditions are required by law.
80
81         SETTING UP ----------------------------------------------------------------------
82
83         Let's get a few housekeeping things out of the way.  Firstly because I need to draw lots of
84         ASCII-art diagrams to explain concepts, the best way to look at this is using a window which
85         uses a fixed width font and is at least this wide:
86
87  <------------------------------------------------------------------------------------------------------------------------>
88
89         Secondly make sure TABS are set to 8 characters.  The following should be a vertical
90         line.  If not, sort out your tabs.
91
92         |
93         |
94         |
95
96         Thirdly I assume that your screen is at least 50 characters high.
97
98         ASSEMBLING ----------------------------------------------------------------------
99
100         If you want to actually run this FORTH, rather than just read it, you will need Linux on an
101         i386.  Linux because instead of programming directly to the hardware on a bare PC which I
102         could have done, I went for a simpler tutorial by assuming that the 'hardware' is a Linux
103         process with a few basic system calls (read, write and exit and that's about all).  i386
104         is needed because I had to write the assembly for a processor, and i386 is by far the most
105         common.  (Of course when I say 'i386', any 32- or 64-bit x86 processor will do.  I'm compiling
106         this on a 64 bit AMD Opteron).
107
108         Again, to assemble this you will need gcc and gas (the GNU assembler).  The commands to
109         assemble and run the code (save this file as 'jonesforth.S') are:
110
111         gcc -m32 -nostdlib -static -Wl,-Ttext,0 -o jonesforth jonesforth.S
112         ./jonesforth
113
114         You will see lots of 'Warning: unterminated string; newline inserted' messages from the
115         assembler.  That's just because the GNU assembler doesn't have a good syntax for multi-line
116         strings (or rather it used to, but the developers removed it!) so I've abused the syntax
117         slightly to make things readable.  Ignore these warnings.
118
119         If you want to run your own FORTH programs you can do:
120
121         ./jonesforth < myprog.f
122
123         If you want to load your own FORTH code and then continue reading user commands, you can do:
124
125         cat myfunctions.f - | ./jonesforth
126
127         ASSEMBLER ----------------------------------------------------------------------
128
129         (You can just skip to the next section -- you don't need to be able to read assembler to
130         follow this tutorial).
131
132         However if you do want to read the assembly code here are a few notes about gas (the GNU assembler):
133
134         (1) Register names are prefixed with '%', so %eax is the 32 bit i386 accumulator.  The registers
135             available on i386 are: %eax, %ebx, %ecx, %edx, %esi, %edi, %ebp and %esp, and most of them
136             have special purposes.
137
138         (2) Add, mov, etc. take arguments in the form SRC,DEST.  So mov %eax,%ecx moves %eax -> %ecx
139
140         (3) Constants are prefixed with '$', and you mustn't forget it!  If you forget it then it
141             causes a read from memory instead, so:
142             mov $2,%eax         moves number 2 into %eax
143             mov 2,%eax          reads the 32 bit word from address 2 into %eax (ie. most likely a mistake)
144
145         (4) gas has a funky syntax for local labels, where '1f' (etc.) means label '1:' "forwards"
146             and '1b' (etc.) means label '1:' "backwards".
147
148         (5) 'ja' is "jump if above", 'jb' for "jump if below", 'je' "jump if equal" etc.
149
150         (6) gas has a reasonably nice .macro syntax, and I use them a lot to make the code shorter and
151             less repetitive.
152
153         For more help reading the assembler, do "info gas" at the Linux prompt.
154
155         Now the tutorial starts in earnest.
156
157         THE DICTIONARY ----------------------------------------------------------------------
158
159         In FORTH as you will know, functions are called "words", and just as in other languages they
160         have a name and a definition.  Here are two FORTH words:
161
162         : DOUBLE DUP + ;                \ name is "DOUBLE", definition is "DUP +"
163         : QUADRUPLE DOUBLE DOUBLE ;     \ name is "QUADRUPLE", definition is "DOUBLE DOUBLE"
164
165         Words, both built-in ones and ones which the programmer defines later, are stored in a dictionary
166         which is just a linked list of dictionary entries.
167
168         <--- DICTIONARY ENTRY (HEADER) ----------------------->
169         +------------------------+--------+---------- - - - - +----------- - - - -
170         | LINK POINTER           | LENGTH/| NAME              | DEFINITION
171         |                        | FLAGS  |                   |
172         +--- (4 bytes) ----------+- byte -+- n bytes  - - - - +----------- - - - -
173
174         I'll come to the definition of the word later.  For now just look at the header.  The first
175         4 bytes are the link pointer.  This points back to the previous word in the dictionary, or, for
176         the first word in the dictionary it is just a NULL pointer.  Then comes a length/flags byte.
177         The length of the word can be up to 31 characters (5 bits used) and the top three bits are used
178         for various flags which I'll come to later.  This is followed by the name itself, and in this
179         implementation the name is rounded up to a multiple of 4 bytes by padding it with zero bytes.
180         That's just to ensure that the definition starts on a 32 bit boundary.
181
182         A FORTH variable called LATEST contains a pointer to the most recently defined word, in
183         other words, the head of this linked list.
184
185         DOUBLE and QUADRUPLE might look like this:
186
187           pointer to previous word
188            ^
189            |
190         +--|------+---+---+---+---+---+---+---+---+------------- - - - -
191         | LINK    | 6 | D | O | U | B | L | E | 0 | (definition ...)
192         +---------+---+---+---+---+---+---+---+---+------------- - - - -
193            ^       len                         padding
194            |
195         +--|------+---+---+---+---+---+---+---+---+---+---+---+---+------------- - - - -
196         | LINK    | 9 | Q | U | A | D | R | U | P | L | E | 0 | 0 | (definition ...)
197         +---------+---+---+---+---+---+---+---+---+---+---+---+---+------------- - - - -
198            ^       len                                     padding
199            |
200            |
201           LATEST
202
203         You shoud be able to see from this how you might implement functions to find a word in
204         the dictionary (just walk along the dictionary entries starting at LATEST and matching
205         the names until you either find a match or hit the NULL pointer at the end of the dictionary);
206         and add a word to the dictionary (create a new definition, set its LINK to LATEST, and set
207         LATEST to point to the new word).  We'll see precisely these functions implemented in
208         assembly code later on.
209
210         One interesting consequence of using a linked list is that you can redefine words, and
211         a newer definition of a word overrides an older one.  This is an important concept in
212         FORTH because it means that any word (even "built-in" or "standard" words) can be
213         overridden with a new definition, either to enhance it, to make it faster or even to
214         disable it.  However because of the way that FORTH words get compiled, which you'll
215         understand below, words defined using the old definition of a word continue to use
216         the old definition.  Only words defined after the new definition use the new definition.
217
218         DIRECT THREADED CODE ----------------------------------------------------------------------
219
220         Now we'll get to the really crucial bit in understanding FORTH, so go and get a cup of tea
221         or coffee and settle down.  It's fair to say that if you don't understand this section, then you
222         won't "get" how FORTH works, and that would be a failure on my part for not explaining it well.
223         So if after reading this section a few times you don't understand it, please email me
224         (rich@annexia.org).
225
226         Let's talk first about what "threaded code" means.  Imagine a peculiar version of C where
227         you are only allowed to call functions without arguments.  (Don't worry for now that such a
228         language would be completely useless!)  So in our peculiar C, code would look like this:
229
230         f ()
231         {
232           a ();
233           b ();
234           c ();
235         }
236
237         and so on.  How would a function, say 'f' above, be compiled by a standard C compiler?
238         Probably into assembly code like this.  On the right hand side I've written the actual
239         i386 machine code.
240
241         f:
242           CALL a                        E8 08 00 00 00
243           CALL b                        E8 1C 00 00 00
244           CALL c                        E8 2C 00 00 00
245           ; ignore the return from the function for now
246
247         "E8" is the x86 machine code to "CALL" a function.  In the first 20 years of computing
248         memory was hideously expensive and we might have worried about the wasted space being used
249         by the repeated "E8" bytes.  We can save 20% in code size (and therefore, in expensive memory)
250         by compressing this into just:
251
252         08 00 00 00             Just the function addresses, without
253         1C 00 00 00             the CALL prefix.
254         2C 00 00 00
255
256         [Historical note: If the execution model that FORTH uses looks strange from the following
257         paragraphs, then it was motivated entirely by the need to save memory on early computers.
258         This code compression isn't so important now when our machines have more memory in their L1
259         caches than those early computers had in total, but the execution model still has some
260         useful properties].
261
262         Of course this code won't run directly any more.  Instead we need to write an interpreter
263         which takes each pair of bytes and calls it.
264
265         On an i386 machine it turns out that we can write this interpreter rather easily, in just
266         two assembly instructions which turn into just 3 bytes of machine code.  Let's store the
267         pointer to the next word to execute in the %esi register:
268
269                 08 00 00 00     <- We're executing this one now.  %esi is the _next_ one to execute.
270         %esi -> 1C 00 00 00
271                 2C 00 00 00
272
273         The all-important i386 instruction is called LODSL (or in Intel manuals, LODSW).  It does
274         two things.  Firstly it reads the memory at %esi into the accumulator (%eax).  Secondly it
275         increments %esi by 4 bytes.  So after LODSL, the situation now looks like this:
276
277                 08 00 00 00     <- We're still executing this one
278                 1C 00 00 00     <- %eax now contains this address (0x0000001C)
279         %esi -> 2C 00 00 00
280
281         Now we just need to jump to the address in %eax.  This is again just a single x86 instruction
282         written JMP *(%eax).  And after doing the jump, the situation looks like:
283
284                 08 00 00 00
285                 1C 00 00 00     <- Now we're executing this subroutine.
286         %esi -> 2C 00 00 00
287
288         To make this work, each subroutine is followed by the two instructions 'LODSL; JMP *(%eax)'
289         which literally make the jump to the next subroutine.
290
291         And that brings us to our first piece of actual code!  Well, it's a macro.
292 */
293
294 /* NEXT macro. */
295         .macro NEXT
296         lodsl
297         jmp *(%eax)
298         .endm
299
300 /*      The macro is called NEXT.  That's a FORTH-ism.  It expands to those two instructions.
301
302         Every FORTH primitive that we write has to be ended by NEXT.  Think of it kind of like
303         a return.
304
305         The above describes what is known as direct threaded code.
306
307         To sum up: We compress our function calls down to a list of addresses and use a somewhat
308         magical macro to act as a "jump to next function in the list".  We also use one register (%esi)
309         to act as a kind of instruction pointer, pointing to the next function in the list.
310
311         I'll just give you a hint of what is to come by saying that a FORTH definition such as:
312
313         : QUADRUPLE DOUBLE DOUBLE ;
314
315         actually compiles (almost, not precisely but we'll see why in a moment) to a list of
316         function addresses for DOUBLE, DOUBLE and a special function called EXIT to finish off.
317
318         At this point, REALLY EAGLE-EYED ASSEMBLY EXPERTS are saying "JONES, YOU'VE MADE A MISTAKE!".
319
320         I lied about JMP *(%eax).  
321
322         INDIRECT THREADED CODE ----------------------------------------------------------------------
323
324         It turns out that direct threaded code is interesting but only if you want to just execute
325         a list of functions written in assembly language.  So QUADRUPLE would work only if DOUBLE
326         was an assembly language function.  In the direct threaded code, QUADRUPLE would look like:
327
328                 +------------------+
329                 | addr of DOUBLE  --------------------> (assembly code to do the double)
330                 +------------------+                    NEXT
331         %esi -> | addr of DOUBLE   |
332                 +------------------+
333
334         We can add an extra indirection to allow us to run both words written in assembly language
335         (primitives written for speed) and words written in FORTH themselves as lists of addresses.
336
337         The extra indirection is the reason for the brackets in JMP *(%eax).
338
339         Let's have a look at how QUADRUPLE and DOUBLE really look in FORTH:
340
341                 : QUADRUPLE DOUBLE DOUBLE ;
342
343                 +------------------+
344                 | codeword         |               : DOUBLE DUP + ;
345                 +------------------+
346                 | addr of DOUBLE  ---------------> +------------------+
347                 +------------------+               | codeword         |
348                 | addr of DOUBLE   |               +------------------+
349                 +------------------+               | addr of DUP   --------------> +------------------+
350                 | addr of EXIT     |               +------------------+            | codeword      -------+
351                 +------------------+       %esi -> | addr of +     --------+       +------------------+   |
352                                                    +------------------+    |       | assembly to    <-----+
353                                                    | addr of EXIT     |    |       | implement DUP    |
354                                                    +------------------+    |       |    ..            |
355                                                                            |       |    ..            |
356                                                                            |       | NEXT             |
357                                                                            |       +------------------+
358                                                                            |
359                                                                            +-----> +------------------+
360                                                                                    | codeword      -------+
361                                                                                    +------------------+   |
362                                                                                    | assembly to   <------+
363                                                                                    | implement +      |
364                                                                                    |    ..            |
365                                                                                    |    ..            |
366                                                                                    | NEXT             |
367                                                                                    +------------------+
368
369         This is the part where you may need an extra cup of tea/coffee/favourite caffeinated
370         beverage.  What has changed is that I've added an extra pointer to the beginning of
371         the definitions.  In FORTH this is sometimes called the "codeword".  The codeword is
372         a pointer to the interpreter to run the function.  For primitives written in
373         assembly language, the "interpreter" just points to the actual assembly code itself.
374         They don't need interpreting, they just run.
375
376         In words written in FORTH (like QUADRUPLE and DOUBLE), the codeword points to an interpreter
377         function.
378
379         I'll show you the interpreter function shortly, but let's recall our indirect
380         JMP *(%eax) with the "extra" brackets.  Take the case where we're executing DOUBLE
381         as shown, and DUP has been called.  Note that %esi is pointing to the address of +
382
383         The assembly code for DUP eventually does a NEXT.  That:
384
385         (1) reads the address of + into %eax            %eax points to the codeword of +
386         (2) increments %esi by 4
387         (3) jumps to the indirect %eax                  jumps to the address in the codeword of +,
388                                                         ie. the assembly code to implement +
389
390                 +------------------+
391                 | codeword         |
392                 +------------------+
393                 | addr of DOUBLE  ---------------> +------------------+
394                 +------------------+               | codeword         |
395                 | addr of DOUBLE   |               +------------------+
396                 +------------------+               | addr of DUP   --------------> +------------------+
397                 | addr of EXIT     |               +------------------+            | codeword      -------+
398                 +------------------+               | addr of +     --------+       +------------------+   |
399                                                    +------------------+    |       | assembly to    <-----+
400                                            %esi -> | addr of EXIT     |    |       | implement DUP    |
401                                                    +------------------+    |       |    ..            |
402                                                                            |       |    ..            |
403                                                                            |       | NEXT             |
404                                                                            |       +------------------+
405                                                                            |
406                                                                            +-----> +------------------+
407                                                                                    | codeword      -------+
408                                                                                    +------------------+   |
409                                                                         now we're  | assembly to   <------+
410                                                                         executing  | implement +      |
411                                                                         this       |    ..            |
412                                                                         function   |    ..            |
413                                                                                    | NEXT             |
414                                                                                    +------------------+
415
416         So I hope that I've convinced you that NEXT does roughly what you'd expect.  This is
417         indirect threaded code.
418
419         I've glossed over four things.  I wonder if you can guess without reading on what they are?
420
421         .
422         .
423         .
424
425         My list of four things are: (1) What does "EXIT" do?  (2) which is related to (1) is how do
426         you call into a function, ie. how does %esi start off pointing at part of QUADRUPLE, but
427         then point at part of DOUBLE.  (3) What goes in the codeword for the words which are written
428         in FORTH?  (4) How do you compile a function which does anything except call other functions
429         ie. a function which contains a number like : DOUBLE 2 * ; ?
430
431         THE INTERPRETER AND RETURN STACK ------------------------------------------------------------
432
433         Going at these in no particular order, let's talk about issues (3) and (2), the interpreter
434         and the return stack.
435
436         Words which are defined in FORTH need a codeword which points to a little bit of code to
437         give them a "helping hand" in life.  They don't need much, but they do need what is known
438         as an "interpreter", although it doesn't really "interpret" in the same way that, say,
439         Java bytecode used to be interpreted (ie. slowly).  This interpreter just sets up a few
440         machine registers so that the word can then execute at full speed using the indirect
441         threaded model above.
442
443         One of the things that needs to happen when QUADRUPLE calls DOUBLE is that we save the old
444         %esi ("instruction pointer") and create a new one pointing to the first word in DOUBLE.
445         Because we will need to restore the old %esi at the end of DOUBLE (this is, after all, like
446         a function call), we will need a stack to store these "return addresses" (old values of %esi).
447
448         As you will have read, when reading the background documentation, FORTH has two stacks,
449         an ordinary stack for parameters, and a return stack which is a bit more mysterious.  But
450         our return stack is just the stack I talked about in the previous paragraph, used to save
451         %esi when calling from a FORTH word into another FORTH word.
452
453         In this FORTH, we are using the normal stack pointer (%esp) for the parameter stack.
454         We will use the i386's "other" stack pointer (%ebp, usually called the "frame pointer")
455         for our return stack.
456
457         I've got two macros which just wrap up the details of using %ebp for the return stack.
458         You use them as for example "PUSHRSP %eax" (push %eax on the return stack) or "POPRSP %ebx"
459         (pop top of return stack into %ebx).
460 */
461
462 /* Macros to deal with the return stack. */
463         .macro PUSHRSP reg
464         lea -4(%ebp),%ebp       // push reg on to return stack
465         movl \reg,(%ebp)
466         .endm
467
468         .macro POPRSP reg
469         mov (%ebp),\reg         // pop top of return stack to reg
470         lea 4(%ebp),%ebp
471         .endm
472
473 /*
474         And with that we can now talk about the interpreter.
475
476         In FORTH the interpreter function is often called DOCOL (I think it means "DO COLON" because
477         all FORTH definitions start with a colon, as in : DOUBLE DUP + ;
478
479         The "interpreter" (it's not really "interpreting") just needs to push the old %esi on the
480         stack and set %esi to the first word in the definition.  Remember that we jumped to the
481         function using JMP *(%eax)?  Well a consequence of that is that conveniently %eax contains
482         the address of this codeword, so just by adding 4 to it we get the address of the first
483         data word.  Finally after setting up %esi, it just does NEXT which causes that first word
484         to run.
485 */
486
487 /* DOCOL - the interpreter! */
488         .text
489         .align 4
490 DOCOL:
491         PUSHRSP %esi            // push %esi on to the return stack
492         addl $4,%eax            // %eax points to codeword, so make
493         movl %eax,%esi          // %esi point to first data word
494         NEXT
495
496 /*
497         Just to make this absolutely clear, let's see how DOCOL works when jumping from QUADRUPLE
498         into DOUBLE:
499
500                 QUADRUPLE:
501                 +------------------+
502                 | codeword         |
503                 +------------------+               DOUBLE:
504                 | addr of DOUBLE  ---------------> +------------------+
505                 +------------------+       %eax -> | addr of DOCOL    |
506         %esi -> | addr of DOUBLE   |               +------------------+
507                 +------------------+               | addr of DUP      |
508                 | addr of EXIT     |               +------------------+
509                 +------------------+               | etc.             |
510
511         First, the call to DOUBLE calls DOCOL (the codeword of DOUBLE).  DOCOL does this:  It
512         pushes the old %esi on the return stack.  %eax points to the codeword of DOUBLE, so we
513         just add 4 on to it to get our new %esi:
514
515                 QUADRUPLE:
516                 +------------------+
517                 | codeword         |
518                 +------------------+               DOUBLE:
519                 | addr of DOUBLE  ---------------> +------------------+
520 top of return   +------------------+       %eax -> | addr of DOCOL    |
521 stack points -> | addr of DOUBLE   |       + 4 =   +------------------+
522                 +------------------+       %esi -> | addr of DUP      |
523                 | addr of EXIT     |               +------------------+
524                 +------------------+               | etc.             |
525
526         Then we do NEXT, and because of the magic of threaded code that increments %esi again
527         and calls DUP.
528
529         Well, it seems to work.
530
531         One minor point here.  Because DOCOL is the first bit of assembly actually to be defined
532         in this file (the others were just macros), and because I usually compile this code with the
533         text segment starting at address 0, DOCOL has address 0.  So if you are disassembling the
534         code and see a word with a codeword of 0, you will immediately know that the word is
535         written in FORTH (it's not an assembler primitive) and so uses DOCOL as the interpreter.
536
537         STARTING UP ----------------------------------------------------------------------
538
539         Now let's get down to nuts and bolts.  When we start the program we need to set up
540         a few things like the return stack.  But as soon as we can, we want to jump into FORTH
541         code (albeit much of the "early" FORTH code will still need to be written as
542         assembly language primitives).
543
544         This is what the set up code does.  Does a tiny bit of house-keeping, sets up the
545         separate return stack (NB: Linux gives us the ordinary parameter stack already), then
546         immediately jumps to a FORTH word called COLD.  COLD stands for cold-start.  In ISO
547         FORTH (but not in this FORTH), COLD can be called at any time to completely reset
548         the state of FORTH, and there is another word called WARM which does a partial reset.
549 */
550
551 /* ELF entry point. */
552         .text
553         .globl _start
554 _start:
555         cld
556         mov %esp,var_S0         // Store the initial data stack pointer.
557         mov $return_stack,%ebp  // Initialise the return stack.
558
559         mov $cold_start,%esi    // Initialise interpreter.
560         NEXT                    // Run interpreter!
561
562         .section .rodata
563 cold_start:                     // High-level code without a codeword.
564         .int COLD
565
566 /*
567         We also allocate some space for the return stack and some space to store user
568         definitions.  These are static memory allocations using fixed-size buffers, but it
569         wouldn't be a great deal of work to make them dynamic.
570 */
571
572         .bss
573 /* FORTH return stack. */
574 #define RETURN_STACK_SIZE 8192
575         .align 4096
576         .space RETURN_STACK_SIZE
577 return_stack:                   // Initial top of return stack.
578
579 /* Space for user-defined words. */
580 #define USER_DEFS_SIZE 16384
581         .align 4096
582 user_defs_start:
583         .space USER_DEFS_SIZE
584
585 /*
586         BUILT-IN WORDS ----------------------------------------------------------------------
587
588         Remember our dictionary entries (headers).  Let's bring those together with the codeword
589         and data words to see how : DOUBLE DUP + ; really looks in memory.
590
591           pointer to previous word
592            ^
593            |
594         +--|------+---+---+---+---+---+---+---+---+------------+------------+------------+------------+
595         | LINK    | 6 | D | O | U | B | L | E | 0 | DOCOL      | DUP        | +          | EXIT       |
596         +---------+---+---+---+---+---+---+---+---+------------+--|---------+------------+------------+
597            ^       len                         pad  codeword      |
598            |                                                      V
599           LINK in next word                             points to codeword of DUP
600         
601         Initially we can't just write ": DOUBLE DUP + ;" (ie. that literal string) here because we
602         don't yet have anything to read the string, break it up at spaces, parse each word, etc. etc.
603         So instead we will have to define built-in words using the GNU assembler data constructors
604         (like .int, .byte, .string, .ascii and so on -- look them up in the gas info page if you are
605         unsure of them).
606
607         The long way would be:
608         .int <link to previous word>
609         .byte 6                 // len
610         .ascii "DOUBLE"         // string
611         .byte 0                 // padding
612 DOUBLE: .int DOCOL              // codeword
613         .int DUP                // pointer to codeword of DUP
614         .int PLUS               // pointer to codeword of +
615         .int EXIT               // pointer to codeword of EXIT
616
617         That's going to get quite tedious rather quickly, so here I define an assembler macro
618         so that I can just write:
619
620         defword "DOUBLE",6,,DOUBLE
621         .int DUP,PLUS,EXIT
622
623         and I'll get exactly the same effect.
624
625         Don't worry too much about the exact implementation details of this macro - it's complicated!
626 */
627
628 /* Flags - these are discussed later. */
629 #define F_IMMED 0x80
630 #define F_HIDDEN 0x20
631
632         // Store the chain of links.
633         .set link,0
634
635         .macro defword name, namelen, flags=0, label
636         .section .rodata
637         .align 4
638         .globl name_\label
639 name_\label :
640         .int link               // link
641         .set link,name_\label
642         .byte \flags+\namelen   // flags + length byte
643         .ascii "\name"          // the name
644         .align 4
645         .globl \label
646 \label :
647         .int DOCOL              // codeword - the interpreter
648         // list of word pointers follow
649         .endm
650
651 /*
652         Similarly I want a way to write words written in assembly language.  There will quite a few
653         of these to start with because, well, everything has to start in assembly before there's
654         enough "infrastructure" to be able to start writing FORTH words, but also I want to define
655         some common FORTH words in assembly language for speed, even though I could write them in FORTH.
656
657         This is what DUP looks like in memory:
658
659           pointer to previous word
660            ^
661            |
662         +--|------+---+---+---+---+------------+
663         | LINK    | 3 | D | U | P | code_DUP ---------------------> points to the assembly
664         +---------+---+---+---+---+------------+                    code used to write DUP,
665            ^       len              codeword                        which ends with NEXT.
666            |
667           LINK in next word
668
669         Again, for brevity in writing the header I'm going to write an assembler macro called defcode.
670 */
671
672         .macro defcode name, namelen, flags=0, label
673         .section .rodata
674         .align 4
675         .globl name_\label
676 name_\label :
677         .int link               // link
678         .set link,name_\label
679         .byte \flags+\namelen   // flags + length byte
680         .ascii "\name"          // the name
681         .align 4
682         .globl \label
683 \label :
684         .int code_\label        // codeword
685         .text
686         .align 4
687         .globl code_\label
688 code_\label :                   // assembler code follows
689         .endm
690
691 /*
692         Now some easy FORTH primitives.  These are written in assembly for speed.  If you understand
693         i386 assembly language then it is worth reading these.  However if you don't understand assembly
694         you can skip the details.
695 */
696
697         defcode "DUP",3,,DUP
698         pop %eax                // duplicate top of stack
699         push %eax
700         push %eax
701         NEXT
702
703         defcode "DROP",4,,DROP
704         pop %eax                // drop top of stack
705         NEXT
706
707         defcode "SWAP",4,,SWAP
708         pop %eax                // swap top of stack
709         pop %ebx
710         push %eax
711         push %ebx
712         NEXT
713
714         defcode "OVER",4,,OVER
715         mov 4(%esp),%eax        // get the second element of stack
716         push %eax               // and push it on top
717         NEXT
718
719         defcode "ROT",3,,ROT
720         pop %eax
721         pop %ebx
722         pop %ecx
723         push %eax
724         push %ecx
725         push %ebx
726         NEXT
727
728         defcode "-ROT",4,,NROT
729         pop %eax
730         pop %ebx
731         pop %ecx
732         push %ebx
733         push %eax
734         push %ecx
735         NEXT
736
737         defcode "1+",2,,INCR
738         incl (%esp)             // increment top of stack
739         NEXT
740
741         defcode "1-",2,,DECR
742         decl (%esp)             // decrement top of stack
743         NEXT
744
745         defcode "4+",2,,INCR4
746         addl $4,(%esp)          // add 4 to top of stack
747         NEXT
748
749         defcode "4-",2,,DECR4
750         subl $4,(%esp)          // subtract 4 from top of stack
751         NEXT
752
753         defcode "+",1,,ADD
754         pop %eax                // get top of stack
755         addl %eax,(%esp)        // and add it to next word on stack
756         NEXT
757
758         defcode "-",1,,SUB
759         pop %eax                // get top of stack
760         subl %eax,(%esp)        // and subtract it from next word on stack
761         NEXT
762
763         defcode "*",1,,MUL
764         pop %eax
765         pop %ebx
766         imull %ebx,%eax
767         push %eax               // ignore overflow
768         NEXT
769
770         defcode "/",1,,DIV
771         xor %edx,%edx
772         pop %ebx
773         pop %eax
774         idivl %ebx
775         push %eax               // push quotient
776         NEXT
777
778         defcode "MOD",3,,MOD
779         xor %edx,%edx
780         pop %ebx
781         pop %eax
782         idivl %ebx
783         push %edx               // push remainder
784         NEXT
785
786         defcode "=",1,,EQU      // top two words are equal?
787         pop %eax
788         pop %ebx
789         cmp %ebx,%eax
790         je 1f
791         pushl $0
792         NEXT
793 1:      pushl $1
794         NEXT
795
796         defcode "<>",2,,NEQU    // top two words are not equal?
797         pop %eax
798         pop %ebx
799         cmp %ebx,%eax
800         je 1f
801         pushl $1
802         NEXT
803 1:      pushl $0
804         NEXT
805
806         defcode "0=",2,,ZEQU    // top of stack equals 0?
807         pop %eax
808         test %eax,%eax
809         jz 1f
810         pushl $0
811         NEXT
812 1:      pushl $1
813         NEXT
814
815         defcode "AND",3,,AND
816         pop %eax
817         andl %eax,(%esp)
818         NEXT
819
820         defcode "OR",2,,OR
821         pop %eax
822         orl %eax,(%esp)
823         NEXT
824
825         defcode "INVERT",6,,INVERT // this is the FORTH "NOT" function
826         notl (%esp)
827         NEXT
828
829 /*
830         RETURNING FROM FORTH WORDS ----------------------------------------------------------------------
831
832         Time to talk about what happens when we EXIT a function.  In this diagram QUADRUPLE has called
833         DOUBLE, and DOUBLE is about to exit (look at where %esi is pointing):
834
835                 QUADRUPLE
836                 +------------------+
837                 | codeword         |
838                 +------------------+               DOUBLE
839                 | addr of DOUBLE  ---------------> +------------------+
840                 +------------------+               | codeword         |
841                 | addr of DOUBLE   |               +------------------+
842                 +------------------+               | addr of DUP      |
843                 | addr of EXIT     |               +------------------+
844                 +------------------+               | addr of +        |
845                                                    +------------------+
846                                            %esi -> | addr of EXIT     |
847                                                    +------------------+
848
849         What happens when the + function does NEXT?  Well, the following code is executed.
850 */
851
852         defcode "EXIT",4,,EXIT
853         POPRSP %esi             // pop return stack into %esi
854         NEXT
855
856 /*
857         EXIT gets the old %esi which we saved from before on the return stack, and puts it in %esi.
858         So after this (but just before NEXT) we get:
859
860                 QUADRUPLE
861                 +------------------+
862                 | codeword         |
863                 +------------------+               DOUBLE
864                 | addr of DOUBLE  ---------------> +------------------+
865                 +------------------+               | codeword         |
866         %esi -> | addr of DOUBLE   |               +------------------+
867                 +------------------+               | addr of DUP      |
868                 | addr of EXIT     |               +------------------+
869                 +------------------+               | addr of +        |
870                                                    +------------------+
871                                                    | addr of EXIT     |
872                                                    +------------------+
873
874         And NEXT just completes the job by, well in this case just by calling DOUBLE again :-)
875
876         LITERALS ----------------------------------------------------------------------
877
878         The final point I "glossed over" before was how to deal with functions that do anything
879         apart from calling other functions.  For example, suppose that DOUBLE was defined like this:
880
881         : DOUBLE 2 * ;
882
883         It does the same thing, but how do we compile it since it contains the literal 2?  One way
884         would be to have a function called "2" (which you'd have to write in assembler), but you'd need
885         a function for every single literal that you wanted to use.
886
887         FORTH solves this by compiling the function using a special word called LIT:
888
889         +---------------------------+-------+-------+-------+-------+-------+
890         | (usual header of DOUBLE)  | DOCOL | LIT   | 2     | *     | EXIT  |
891         +---------------------------+-------+-------+-------+-------+-------+
892
893         LIT is executed in the normal way, but what it does next is definitely not normal.  It
894         looks at %esi (which now points to the literal 2), grabs it, pushes it on the stack, then
895         manipulates %esi in order to skip the literal as if it had never been there.
896
897         What's neat is that the whole grab/manipulate can be done using a single byte single
898         i386 instruction, our old friend LODSL.  Rather than me drawing more ASCII-art diagrams,
899         see if you can find out how LIT works:
900 */
901
902         defcode "LIT",3,,LIT
903         // %esi points to the next command, but in this case it points to the next
904         // literal 32 bit integer.  Get that literal into %eax and increment %esi.
905         // On x86, it's a convenient single byte instruction!  (cf. NEXT macro)
906         lodsl
907         push %eax               // push the literal number on to stack
908         NEXT
909
910 /*
911         MEMORY ----------------------------------------------------------------------
912
913         As important point about FORTH is that it gives you direct access to the lowest levels
914         of the machine.  Manipulating memory directly is done frequently in FORTH, and these are
915         the primitive words for doing it.
916 */
917
918         defcode "!",1,,STORE
919         pop %ebx                // address to store at
920         pop %eax                // data to store there
921         mov %eax,(%ebx)         // store it
922         NEXT
923
924         defcode "@",1,,FETCH
925         pop %ebx                // address to fetch
926         mov (%ebx),%eax         // fetch it
927         push %eax               // push value onto stack
928         NEXT
929
930         defcode "+!",2,,ADDSTORE
931         pop %ebx                // address
932         pop %eax                // the amount to add
933         addl %eax,(%ebx)        // add it
934         NEXT
935
936         defcode "-!",2,,SUBSTORE
937         pop %ebx                // address
938         pop %eax                // the amount to subtract
939         subl %eax,(%ebx)        // add it
940         NEXT
941
942 /* ! and @ (STORE and FETCH) store 32-bit words.  It's also useful to be able to read and write bytes.
943  * I don't know whether FORTH has these words, so I invented my own, called !b and @b.
944  * Byte-oriented operations only work on architectures which permit them (i386 is one of those).
945  * UPDATE: writing a byte to the dictionary pointer is called C, in FORTH.
946  */
947         defcode "!b",2,,STOREBYTE
948         pop %ebx                // address to store at
949         pop %eax                // data to store there
950         movb %al,(%ebx)         // store it
951         NEXT
952
953         defcode "@b",2,,FETCHBYTE
954         pop %ebx                // address to fetch
955         xor %eax,%eax
956         movb (%ebx),%al         // fetch it
957         push %eax               // push value onto stack
958         NEXT
959
960 /*
961         BUILT-IN VARIABLES ----------------------------------------------------------------------
962
963         These are some built-in variables and related standard FORTH words.  Of these, the only one that we
964         have discussed so far was LATEST, which points to the last (most recently defined) word in the
965         FORTH dictionary.  LATEST is also a FORTH word which pushes the address of LATEST (the variable)
966         on to the stack, so you can read or write it using @ and ! operators.  For example, to print
967         the current value of LATEST (and this can apply to any FORTH variable) you would do:
968
969         LATEST @ . CR
970
971         To make defining variables shorter, I'm using a macro called defvar, similar to defword and
972         defcode above.  (In fact the defvar macro uses defcode to do the dictionary header).
973 */
974
975         .macro defvar name, namelen, flags=0, label, initial=0
976         defcode \name,\namelen,\flags,\label
977         push $var_\name
978         NEXT
979         .data
980         .align 4
981 var_\name :
982         .int \initial
983         .endm
984
985 /*
986         The built-in variables are:
987
988         STATE           Is the interpreter executing code (0) or compiling a word (non-zero)?
989         LATEST          Points to the latest (most recently defined) word in the dictionary.
990         HERE            Points to the next free byte of memory.  When compiling, compiled words go here.
991         _X              These are three scratch variables, used by some standard dictionary words.
992         _Y
993         _Z
994         S0              Stores the address of the top of the parameter stack.
995         R0              Stores the address of the top of the return stack.
996
997 */
998         defvar "STATE",5,,STATE
999         defvar "HERE",4,,HERE,user_defs_start
1000         defvar "LATEST",6,,LATEST,name_SYSEXIT // SYSEXIT must be last in built-in dictionary
1001         defvar "_X",2,,TX
1002         defvar "_Y",2,,TY
1003         defvar "_Z",2,,TZ
1004         defvar "S0",2,,SZ
1005         defvar "R0",2,,RZ,return_stack
1006
1007 /*
1008         RETURN STACK ----------------------------------------------------------------------
1009
1010         These words allow you to access the return stack.  Recall that the register %ebp always points to
1011         the top of the return stack.
1012 */
1013
1014         defcode ">R",2,,TOR
1015         pop %eax                // pop parameter stack into %eax
1016         PUSHRSP %eax            // push it on to the return stack
1017         NEXT
1018
1019         defcode "R>",2,,FROMR
1020         POPRSP %eax             // pop return stack on to %eax
1021         push %eax               // and push on to parameter stack
1022         NEXT
1023
1024         defcode "RSP@",4,,RSPFETCH
1025         push %ebp
1026         NEXT
1027
1028         defcode "RSP!",4,,RSPSTORE
1029         pop %ebp
1030         NEXT
1031
1032         defcode "RDROP",5,,RDROP
1033         lea 4(%ebp),%ebp        // pop return stack and throw away
1034         NEXT
1035
1036 /*
1037         PARAMETER (DATA) STACK ----------------------------------------------------------------------
1038
1039         These functions allow you to manipulate the parameter stack.  Recall that Linux sets up the parameter
1040         stack for us, and it is accessed through %esp.
1041 */
1042
1043         defcode "DSP@",4,,DSPFETCH
1044         mov %esp,%eax
1045         push %eax
1046         NEXT
1047
1048         defcode "DSP!",4,,DSPSTORE
1049         pop %esp
1050         NEXT
1051
1052 /*
1053         INPUT AND OUTPUT ----------------------------------------------------------------------
1054
1055         These are our first really meaty/complicated FORTH primitives.  I have chosen to write them in
1056         assembler, but surprisingly in "real" FORTH implementations these are often written in terms
1057         of more fundamental FORTH primitives.  I chose to avoid that because I think that just obscures
1058         the implementation.  After all, you may not understand assembler but you can just think of it
1059         as an opaque block of code that does what it says.
1060
1061         Let's discuss input first.
1062
1063         The FORTH word KEY reads the next byte from stdin (and pushes it on the parameter stack).
1064         So if KEY is called and someone hits the space key, then the number 32 (ASCII code of space)
1065         is pushed on the stack.
1066
1067         In FORTH there is no distinction between reading code and reading input.  We might be reading
1068         and compiling code, we might be reading words to execute, we might be asking for the user
1069         to type their name -- ultimately it all comes in through KEY.
1070
1071         The implementation of KEY uses an input buffer of a certain size (defined at the end of the
1072         program).  It calls the Linux read(2) system call to fill this buffer and tracks its position
1073         in the buffer using a couple of variables, and if it runs out of input buffer then it refills
1074         it automatically.  The other thing that KEY does is if it detects that stdin has closed, it
1075         exits the program, which is why when you hit ^D the FORTH system cleanly exits.
1076 */
1077
1078 #include <asm-i386/unistd.h>
1079
1080         defcode "KEY",3,,KEY
1081         call _KEY
1082         push %eax               // push return value on stack
1083         NEXT
1084 _KEY:
1085         mov (currkey),%ebx
1086         cmp (bufftop),%ebx
1087         jge 1f
1088         xor %eax,%eax
1089         mov (%ebx),%al
1090         inc %ebx
1091         mov %ebx,(currkey)
1092         ret
1093
1094 1:      // out of input; use read(2) to fetch more input from stdin
1095         xor %ebx,%ebx           // 1st param: stdin
1096         mov $buffer,%ecx        // 2nd param: buffer
1097         mov %ecx,currkey
1098         mov $buffend-buffer,%edx // 3rd param: max length
1099         mov $__NR_read,%eax     // syscall: read
1100         int $0x80
1101         test %eax,%eax          // If %eax <= 0, then exit.
1102         jbe 2f
1103         addl %eax,%ecx          // buffer+%eax = bufftop
1104         mov %ecx,bufftop
1105         jmp _KEY
1106
1107 2:      // error or out of input: exit
1108         xor %ebx,%ebx
1109         mov $__NR_exit,%eax     // syscall: exit
1110         int $0x80
1111
1112 /*
1113         By contrast, output is much simpler.  The FORTH word EMIT writes out a single byte to stdout.
1114         This implementation just uses the write system call.  No attempt is made to buffer output, but
1115         it would be a good exercise to add it.
1116 */
1117
1118         defcode "EMIT",4,,EMIT
1119         pop %eax
1120         call _EMIT
1121         NEXT
1122 _EMIT:
1123         mov $1,%ebx             // 1st param: stdout
1124
1125         // write needs the address of the byte to write
1126         mov %al,(2f)
1127         mov $2f,%ecx            // 2nd param: address
1128
1129         mov $1,%edx             // 3rd param: nbytes = 1
1130
1131         mov $__NR_write,%eax    // write syscall
1132         int $0x80
1133         ret
1134
1135         .bss
1136 2:      .space 1                // scratch used by EMIT
1137
1138 /*
1139         Back to input, WORD is a FORTH word which reads the next full word of input.
1140
1141         What it does in detail is that it first skips any blanks (spaces, tabs, newlines and so on).
1142         Then it calls KEY to read characters into an internal buffer until it hits a blank.  Then it
1143         calculates the length of the word it read and returns the address and the length as
1144         two words on the stack (with address at the top).
1145
1146         Notice that WORD has a single internal buffer which it overwrites each time (rather like
1147         a static C string).  Also notice that WORD's internal buffer is just 32 bytes long and
1148         there is NO checking for overflow.  31 bytes happens to be the maximum length of a
1149         FORTH word that we support, and that is what WORD is used for: to read FORTH words when
1150         we are compiling and executing code.  The returned strings are not NUL-terminated, so
1151         in some crazy-world you could define FORTH words containing ASCII NULs, although why
1152         you'd want to is a bit beyond me.
1153
1154         WORD is not suitable for just reading strings (eg. user input) because of all the above
1155         peculiarities and limitations.
1156
1157         Note that when executing, you'll see:
1158         WORD FOO
1159         which puts "FOO" and length 3 on the stack, but when compiling:
1160         : BAR WORD FOO ;
1161         is an error (or at least it doesn't do what you might expect).  Later we'll talk about compiling
1162         and immediate mode, and you'll understand why.
1163 */
1164
1165         defcode "WORD",4,,WORD
1166         call _WORD
1167         push %ecx               // push length
1168         push %edi               // push base address
1169         NEXT
1170
1171 _WORD:
1172         /* Search for first non-blank character.  Also skip \ comments. */
1173 1:
1174         call _KEY               // get next key, returned in %eax
1175         cmpb $'\\',%al          // start of a comment?
1176         je 3f                   // if so, skip the comment
1177         cmpb $' ',%al
1178         jbe 1b                  // if so, keep looking
1179
1180         /* Search for the end of the word, storing chars as we go. */
1181         mov $5f,%edi            // pointer to return buffer
1182 2:
1183         stosb                   // add character to return buffer
1184         call _KEY               // get next key, returned in %al
1185         cmpb $' ',%al           // is blank?
1186         ja 2b                   // if not, keep looping
1187
1188         /* Return the word (well, the static buffer) and length. */
1189         sub $5f,%edi
1190         mov %edi,%ecx           // return length of the word
1191         mov $5f,%edi            // return address of the word
1192         ret
1193
1194         /* Code to skip \ comments to end of the current line. */
1195 3:
1196         call _KEY
1197         cmpb $'\n',%al          // end of line yet?
1198         jne 3b
1199         jmp 1b
1200
1201         .bss
1202         // A static buffer where WORD returns.  Subsequent calls
1203         // overwrite this buffer.  Maximum word length is 32 chars.
1204 5:      .space 32
1205
1206 /*
1207         . (also called DOT) prints the top of the stack as an integer.  In real FORTH implementations
1208         it should print it in the current base, but this assembler version is simpler and can only
1209         print in base 10.
1210
1211         Remember that you can override even built-in FORTH words easily, so if you want to write a
1212         more advanced DOT then you can do so easily at a later point, and probably in FORTH.
1213 */
1214
1215         defcode ".",1,,DOT
1216         pop %eax                // Get the number to print into %eax
1217         call _DOT               // Easier to do this recursively ...
1218         NEXT
1219 _DOT:
1220         mov $10,%ecx            // Base 10
1221 1:
1222         cmp %ecx,%eax
1223         jb 2f
1224         xor %edx,%edx           // %edx:%eax / %ecx -> quotient %eax, remainder %edx
1225         idivl %ecx
1226         pushl %edx
1227         call _DOT
1228         popl %eax
1229         jmp 1b
1230 2:
1231         xor %ah,%ah
1232         aam $10
1233         cwde
1234         addl $'0',%eax
1235         call _EMIT
1236         ret
1237
1238 /*
1239         Almost the opposite of DOT (but not quite), SNUMBER parses a numeric string such as one returned
1240         by WORD and pushes the number on the parameter stack.
1241
1242         This function does absolutely no error checking, and in particular the length of the string
1243         must be >= 1 bytes, and should contain only digits 0-9.  If it doesn't you'll get random results.
1244
1245         This function is only used when reading literal numbers in code, and shouldn't really be used
1246         in user code at all.
1247 */
1248         defcode "SNUMBER",7,,SNUMBER
1249         pop %edi
1250         pop %ecx
1251         call _SNUMBER
1252         push %eax
1253         NEXT
1254 _SNUMBER:
1255         xor %eax,%eax
1256         xor %ebx,%ebx
1257 1:
1258         imull $10,%eax          // %eax *= 10
1259         movb (%edi),%bl
1260         inc %edi
1261         subb $'0',%bl           // ASCII -> digit
1262         add %ebx,%eax
1263         dec %ecx
1264         jnz 1b
1265         ret
1266
1267 /*
1268         DICTIONARY LOOK UPS ----------------------------------------------------------------------
1269
1270         We're building up to our prelude on how FORTH code is compiled, but first we need yet more infrastructure.
1271
1272         The FORTH word FIND takes a string (a word as parsed by WORD -- see above) and looks it up in the
1273         dictionary.  What it actually returns is the address of the dictionary header, if it finds it,
1274         or 0 if it didn't.
1275
1276         So if DOUBLE is defined in the dictionary, then WORD DOUBLE FIND returns the following pointer:
1277
1278     pointer to this
1279         |
1280         |
1281         V
1282         +---------+---+---+---+---+---+---+---+---+------------+------------+------------+------------+
1283         | LINK    | 6 | D | O | U | B | L | E | 0 | DOCOL      | DUP        | +          | EXIT       |
1284         +---------+---+---+---+---+---+---+---+---+------------+------------+------------+------------+
1285
1286         See also >CFA which takes a dictionary entry pointer and returns a pointer to the codeword.
1287
1288         FIND doesn't find dictionary entries which are flagged as HIDDEN.  See below for why.
1289 */
1290
1291         defcode "FIND",4,,FIND
1292         pop %edi                // %edi = address
1293         pop %ecx                // %ecx = length
1294         call _FIND
1295         push %eax
1296         NEXT
1297
1298 _FIND:
1299         push %esi               // Save %esi so we can use it in string comparison.
1300
1301         // Now we start searching backwards through the dictionary for this word.
1302         mov var_LATEST,%edx     // LATEST points to name header of the latest word in the dictionary
1303 1:
1304         test %edx,%edx          // NULL pointer?  (end of the linked list)
1305         je 4f
1306
1307         // Compare the length expected and the length of the word.
1308         // Note that if the F_HIDDEN flag is set on the word, then by a bit of trickery
1309         // this won't pick the word (the length will appear to be wrong).
1310         xor %eax,%eax
1311         movb 4(%edx),%al        // %al = flags+length field
1312         andb $(F_HIDDEN|0x1f),%al // %al = name length
1313         cmpb %cl,%al            // Length is the same?
1314         jne 2f
1315
1316         // Compare the strings in detail.
1317         push %ecx               // Save the length
1318         push %edi               // Save the address (repe cmpsb will move this pointer)
1319         lea 5(%edx),%esi        // Dictionary string we are checking against.
1320         repe cmpsb              // Compare the strings.
1321         pop %edi
1322         pop %ecx
1323         jne 2f                  // Not the same.
1324
1325         // The strings are the same - return the header pointer in %eax
1326         pop %esi
1327         mov %edx,%eax
1328         ret
1329
1330 2:
1331         mov (%edx),%edx         // Move back through the link field to the previous word
1332         jmp 1b                  // .. and loop.
1333
1334 4:      // Not found.
1335         pop %esi
1336         xor %eax,%eax           // Return zero to indicate not found.
1337         ret
1338
1339 /*
1340         FIND returns the dictionary pointer, but when compiling we need the codeword pointer (recall
1341         that FORTH definitions are compiled into lists of codeword pointers).  The standard FORTH
1342         word >CFA turns a dictionary pointer into a codeword pointer.
1343
1344         The example below shows the result of:
1345
1346                 WORD DOUBLE FIND >CFA
1347
1348         FIND returns a pointer to this
1349         |                               >CFA converts it to a pointer to this
1350         |                                          |
1351         V                                          V
1352         +---------+---+---+---+---+---+---+---+---+------------+------------+------------+------------+
1353         | LINK    | 6 | D | O | U | B | L | E | 0 | DOCOL      | DUP        | +          | EXIT       |
1354         +---------+---+---+---+---+---+---+---+---+------------+------------+------------+------------+
1355
1356         Notes:
1357
1358         Because names vary in length, this isn't just a simple increment.
1359
1360         In this FORTH you cannot easily turn a codeword pointer back into a dictionary entry pointer, but
1361         that is not true in most FORTH implementations where they store a back pointer in the definition
1362         (with an obvious memory/complexity cost).  The reason they do this is that it is useful to be
1363         able to go backwards (codeword -> dictionary entry) in order to decompile FORTH definitions.
1364
1365         What does CFA stand for?  My best guess is "Code Field Address".
1366 */
1367
1368         defcode ">CFA",4,,TCFA
1369         pop %edi
1370         call _TCFA
1371         push %edi
1372         NEXT
1373 _TCFA:
1374         xor %eax,%eax
1375         add $4,%edi             // Skip link pointer.
1376         movb (%edi),%al         // Load flags+len into %al.
1377         inc %edi                // Skip flags+len byte.
1378         andb $0x1f,%al          // Just the length, not the flags.
1379         add %eax,%edi           // Skip the name.
1380         addl $3,%edi            // The codeword is 4-byte aligned.
1381         andl $~3,%edi
1382         ret
1383
1384 /*
1385         COMPILING ----------------------------------------------------------------------
1386
1387         Now we'll talk about how FORTH compiles words.  Recall that a word definition looks like this:
1388
1389                 : DOUBLE DUP + ;
1390
1391         and we have to turn this into:
1392
1393           pointer to previous word
1394            ^
1395            |
1396         +--|------+---+---+---+---+---+---+---+---+------------+------------+------------+------------+
1397         | LINK    | 6 | D | O | U | B | L | E | 0 | DOCOL      | DUP        | +          | EXIT       |
1398         +---------+---+---+---+---+---+---+---+---+------------+--|---------+------------+------------+
1399            ^       len                         pad  codeword      |
1400            |                                                      V
1401           LATEST points here                            points to codeword of DUP
1402
1403         There are several problems to solve.  Where to put the new word?  How do we read words?  How
1404         do we define the words : (COLON) and ; (SEMICOLON)?
1405
1406         FORTH solves this rather elegantly and as you might expect in a very low-level way which
1407         allows you to change how the compiler works on your own code.
1408
1409         FORTH has an INTERPRETER function (a true interpreter this time, not DOCOL) which runs in a
1410         loop, reading words (using WORD), looking them up (using FIND), turning them into codeword
1411         pointers (using >CFA) and deciding what to do with them.
1412
1413         What it does depends on the mode of the interpreter (in variable STATE).
1414
1415         When STATE is zero, the interpreter just runs each word as it looks them up.  This is known as
1416         immediate mode.
1417
1418         The interesting stuff happens when STATE is non-zero -- compiling mode.  In this mode the
1419         interpreter appends the codeword pointer to user memory (the HERE variable points to the next
1420         free byte of user memory).
1421
1422         So you may be able to see how we could define : (COLON).  The general plan is:
1423
1424         (1) Use WORD to read the name of the function being defined.
1425
1426         (2) Construct the dictionary entry -- just the header part -- in user memory:
1427
1428     pointer to previous word (from LATEST)                      +-- Afterwards, HERE points here, where
1429            ^                                                    |   the interpreter will start appending
1430            |                                                    V   codewords.
1431         +--|------+---+---+---+---+---+---+---+---+------------+
1432         | LINK    | 6 | D | O | U | B | L | E | 0 | DOCOL      |
1433         +---------+---+---+---+---+---+---+---+---+------------+
1434                    len                         pad  codeword
1435
1436         (3) Set LATEST to point to the newly defined word, ...
1437
1438         (4) .. and most importantly leave HERE pointing just after the new codeword.  This is where
1439             the interpreter will append codewords.
1440
1441         (5) Set STATE to 1.  This goes into compile mode so the interpreter starts appending codewords to
1442             our partially-formed header.
1443
1444         After : has run, our input is here:
1445
1446         : DOUBLE DUP + ;
1447                  ^
1448                  |
1449                 Next byte returned by KEY
1450
1451         so the interpreter (now it's in compile mode, so I guess it's really the compiler) reads DUP,
1452         gets its codeword pointer, and appends it:
1453
1454                                                                              +-- HERE updated to point here.
1455                                                                              |
1456                                                                              V
1457         +---------+---+---+---+---+---+---+---+---+------------+------------+
1458         | LINK    | 6 | D | O | U | B | L | E | 0 | DOCOL      | DUP        |
1459         +---------+---+---+---+---+---+---+---+---+------------+------------+
1460                    len                         pad  codeword
1461
1462         Next we read +, get the codeword pointer, and append it:
1463
1464                                                                                           +-- HERE updated to point here.
1465                                                                                           |
1466                                                                                           V
1467         +---------+---+---+---+---+---+---+---+---+------------+------------+------------+
1468         | LINK    | 6 | D | O | U | B | L | E | 0 | DOCOL      | DUP        | +          |
1469         +---------+---+---+---+---+---+---+---+---+------------+------------+------------+
1470                    len                         pad  codeword
1471
1472         The issue is what happens next.  Obviously what we _don't_ want to happen is that we
1473         read ";" and compile it and go on compiling everything afterwards.
1474
1475         At this point, FORTH uses a trick.  Remember the length byte in the dictionary definition
1476         isn't just a plain length byte, but can also contain flags.  One flag is called the
1477         IMMEDIATE flag (F_IMMED in this code).  If a word in the dictionary is flagged as
1478         IMMEDIATE then the interpreter runs it immediately _even if it's in compile mode_.
1479
1480         I hope I don't need to explain that ; (SEMICOLON) just such a word, flagged as IMMEDIATE.
1481         And all it does is append the codeword for EXIT on to the current definition and switch
1482         back to immediate mode (set STATE back to 0).  Shortly we'll see the actual definition
1483         of ; and we'll see that it's really a very simple definition, declared IMMEDIATE.
1484
1485         After the interpreter reads ; and executes it 'immediately', we get this:
1486
1487         +---------+---+---+---+---+---+---+---+---+------------+------------+------------+------------+
1488         | LINK    | 6 | D | O | U | B | L | E | 0 | DOCOL      | DUP        | +          | EXIT       |
1489         +---------+---+---+---+---+---+---+---+---+------------+------------+------------+------------+
1490                    len                         pad  codeword                                           ^
1491                                                                                                        |
1492                                                                                                       HERE
1493
1494         STATE is set to 0.
1495
1496         And that's it, job done, our new definition is compiled, and we're back in immediate mode
1497         just reading and executing words, perhaps including a call to test our new word DOUBLE.
1498
1499         The only last wrinkle in this is that while our word was being compiled, it was in a
1500         half-finished state.  We certainly wouldn't want DOUBLE to be called somehow during
1501         this time.  There are several ways to stop this from happening, but in FORTH what we
1502         do is flag the word with the HIDDEN flag (F_HIDDEN in this code) just while it is
1503         being compiled.  This prevents FIND from finding it, and thus in theory stops any
1504         chance of it being called.
1505
1506         Compared to the description above, the actual definition of : (COLON) is comparatively simple:
1507 */
1508
1509         defcode ":",1,,COLON
1510
1511         // Get the word and create a dictionary entry header for it.
1512         call _WORD              // Returns %ecx = length, %edi = pointer to word.
1513         mov %edi,%ebx           // %ebx = address of the word
1514
1515         movl var_HERE,%edi      // %edi is the address of the header
1516         movl var_LATEST,%eax    // Get link pointer
1517         stosl                   // and store it in the header.
1518
1519         mov %cl,%al             // Get the length.
1520         orb $F_HIDDEN,%al       // Set the HIDDEN flag on this entry.
1521         stosb                   // Store the length/flags byte.
1522         push %esi
1523         mov %ebx,%esi           // %esi = word
1524         rep movsb               // Copy the word
1525         pop %esi
1526         addl $3,%edi            // Align to next 4 byte boundary.
1527         andl $~3,%edi
1528
1529         movl $DOCOL,%eax        // The codeword for user-created words is always DOCOL (the interpreter)
1530         stosl
1531
1532         // Header built, so now update LATEST and HERE.
1533         // We'll be compiling words and putting them HERE.
1534         movl var_HERE,%eax
1535         movl %eax,var_LATEST
1536         movl %edi,var_HERE
1537
1538         // And go into compile mode by setting STATE to 1.
1539         movl $1,var_STATE
1540         NEXT
1541
1542 /*
1543         , (COMMA) is a standard FORTH word which appends a 32 bit integer (normally a codeword
1544         pointer) to the user data area pointed to by HERE, and adds 4 to HERE.
1545 */
1546
1547         defcode ",",1,,COMMA
1548         pop %eax                // Code pointer to store.
1549         call _COMMA
1550         NEXT
1551 _COMMA:
1552         movl var_HERE,%edi      // HERE
1553         stosl                   // Store it.
1554         movl %edi,var_HERE      // Update HERE (incremented)
1555         ret
1556
1557 /*
1558         ; (SEMICOLON) is also elegantly simple.  Notice the F_IMMED flag.
1559 */
1560
1561         defcode ";",1,F_IMMED,SEMICOLON
1562         movl $EXIT,%eax         // EXIT is the final codeword in compiled words.
1563         call _COMMA             // Store it.
1564         call _HIDDEN            // Toggle the HIDDEN flag (unhides the new word).
1565         xor %eax,%eax           // Set STATE to 0 (back to execute mode).
1566         movl %eax,var_STATE
1567         NEXT
1568
1569 /*
1570         EXTENDING THE COMPILER ----------------------------------------------------------------------
1571
1572         Words flagged with IMMEDIATE (F_IMMED) aren't just for the FORTH compiler to use.  You can define
1573         your own IMMEDIATE words too, and this is a crucial aspect when extending basic FORTH, because
1574         it allows you in effect to extend the compiler itself.  Does gcc let you do that?
1575
1576         Standard FORTH words like IF, WHILE, .", [ and so on are all written as extensions to the basic
1577         compiler, and are all IMMEDIATE words.
1578
1579         The IMMEDIATE word toggles the F_IMMED (IMMEDIATE flag) on the most recently defined word,
1580         or on the current word if you call it in the middle of a definition.
1581
1582         Typical usage is:
1583
1584         : MYIMMEDWORD IMMEDIATE
1585                 ...definition...
1586         ;
1587
1588         but some FORTH programmers write this instead:
1589
1590         : MYIMMEDWORD
1591                 ...definition...
1592         ; IMMEDIATE
1593
1594         The two usages are equivalent, to a first approximation.
1595 */
1596
1597         defcode "IMMEDIATE",9,F_IMMED,IMMEDIATE
1598         call _IMMEDIATE
1599         NEXT
1600 _IMMEDIATE:
1601         movl var_LATEST,%edi    // LATEST word.
1602         addl $4,%edi            // Point to name/flags byte.
1603         xorb $F_IMMED,(%edi)    // Toggle the IMMED bit.
1604         ret
1605
1606 /*
1607         HIDDEN toggles the other flag, F_HIDDEN, of the latest word.  Note that words flagged
1608         as hidden are defined but cannot be called, so this is rarely used.
1609 */
1610
1611         defcode "HIDDEN",6,,HIDDEN
1612         call _HIDDEN
1613         NEXT
1614 _HIDDEN:
1615         movl var_LATEST,%edi    // LATEST word.
1616         addl $4,%edi            // Point to name/flags byte.
1617         xorb $F_HIDDEN,(%edi)   // Toggle the HIDDEN bit.
1618         ret
1619
1620 /*
1621         ' (TICK) is a standard FORTH word which returns the codeword pointer of the next word.
1622
1623         The common usage is:
1624
1625         ' FOO ,
1626
1627         which appends the codeword of FOO to the current word we are defining (this only works in compiled code).
1628
1629         You tend to use ' in IMMEDIATE words.  For example an alternate (and rather useless) way to define
1630         a literal 2 might be:
1631
1632         : LIT2 IMMEDIATE
1633                 ' LIT ,         \ Appends LIT to the currently-being-defined word
1634                 2 ,             \ Appends the number 2 to the currently-being-defined word
1635         ;
1636
1637         So you could do:
1638
1639         : DOUBLE LIT2 * ;
1640
1641         (If you don't understand how LIT2 works, then you should review the material about compiling words
1642         and immediate mode).
1643
1644         This definition of ' uses a cheat which I copied from buzzard92.  As a result it only works in
1645         compiled code.  It is possible to write a version of ' based on WORD, FIND, >CFA which works in
1646         immediate mode too.
1647 */
1648         defcode "'",1,,TICK
1649         lodsl                   // Get the address of the next word and skip it.
1650         pushl %eax              // Push it on the stack.
1651         NEXT
1652
1653 /*
1654         BRANCHING ----------------------------------------------------------------------
1655
1656         It turns out that all you need in order to define looping constructs, IF-statements, etc.
1657         are two primitives.
1658
1659         BRANCH is an unconditional branch. 0BRANCH is a conditional branch (it only branches if the
1660         top of stack is zero).
1661
1662         The diagra below shows how BRANCH works in some imaginary compiled word.  When BRANCH executes,
1663         %esi starts by pointing to the offset field (compare to LIT above):
1664
1665         +---------------------+-------+---- - - ---+------------+------------+---- - - - ----+------------+
1666         | (Dictionary header) | DOCOL |            | BRANCH     | offset     | (skipped)     | word       |
1667         +---------------------+-------+---- - - ---+------------+-----|------+---- - - - ----+------------+
1668                                                                    ^  |                       ^
1669                                                                    |  |                       |
1670                                                                    |  +-----------------------+
1671                                                                   %esi added to offset
1672
1673         The offset is added to %esi to make the new %esi, and the result is that when NEXT runs, execution
1674         continues at the branch target.  Negative offsets work as expected.
1675
1676         0BRANCH is the same except the branch happens conditionally.
1677
1678         Now standard FORTH words such as IF, THEN, ELSE, WHILE, REPEAT, etc. can be implemented entirely
1679         in FORTH.  They are IMMEDIATE words which append various combinations of BRANCH or 0BRANCH
1680         into the word currently being compiled.
1681
1682         As an example, code written like this:
1683
1684                 condition-code IF true-part THEN rest-code
1685
1686         compiles to:
1687
1688                 condition-code 0BRANCH OFFSET true-part rest-code
1689                                           |             ^
1690                                           |             |
1691                                           +-------------+
1692 */
1693
1694         defcode "BRANCH",6,,BRANCH
1695         add (%esi),%esi         // add the offset to the instruction pointer
1696         NEXT
1697
1698         defcode "0BRANCH",7,,ZBRANCH
1699         pop %eax
1700         test %eax,%eax          // top of stack is zero?
1701         jz code_BRANCH          // if so, jump back to the branch function above
1702         lodsl                   // otherwise we need to skip the offset
1703         NEXT
1704
1705 /*
1706         PRINTING STRINGS ----------------------------------------------------------------------
1707
1708         LITSTRING and EMITSTRING are primitives used to implement the ." operator (which is
1709         written in FORTH).  See the definition of that operator below.
1710 */
1711
1712         defcode "LITSTRING",9,,LITSTRING
1713         lodsl                   // get the length of the string
1714         push %eax               // push it on the stack
1715         push %esi               // push the address of the start of the string
1716         addl %eax,%esi          // skip past the string
1717         addl $3,%esi            // but round up to next 4 byte boundary
1718         andl $~3,%esi
1719         NEXT
1720
1721         defcode "EMITSTRING",10,,EMITSTRING
1722         mov $1,%ebx             // 1st param: stdout
1723         pop %ecx                // 2nd param: address of string
1724         pop %edx                // 3rd param: length of string
1725         mov $__NR_write,%eax    // write syscall
1726         int $0x80
1727         NEXT
1728
1729 /*
1730         COLD START AND INTERPRETER ----------------------------------------------------------------------
1731
1732         COLD is the first FORTH function called, almost immediately after the FORTH system "boots".
1733
1734         INTERPRETER is the FORTH interpreter ("toploop", "toplevel" or "REPL" might be a more accurate
1735         description -- see: http://en.wikipedia.org/wiki/REPL).
1736 */
1737
1738
1739         // COLD must not return (ie. must not call EXIT).
1740         defword "COLD",4,,COLD
1741         .int INTERPRETER        // call the interpreter loop (never returns)
1742         .int LIT,1,SYSEXIT      // hmmm, but in case it does, exit(1).
1743
1744 /* This interpreter is pretty simple, but remember that in FORTH you can always override
1745  * it later with a more powerful one!
1746  */
1747         defword "INTERPRETER",11,,INTERPRETER
1748         .int INTERPRET,RDROP,INTERPRETER
1749
1750         defcode "INTERPRET",9,,INTERPRET
1751         call _WORD              // Returns %ecx = length, %edi = pointer to word.
1752
1753         // Is it in the dictionary?
1754         xor %eax,%eax
1755         movl %eax,interpret_is_lit // Not a literal number (not yet anyway ...)
1756         call _FIND              // Returns %eax = pointer to header or 0 if not found.
1757         test %eax,%eax          // Found?
1758         jz 1f
1759
1760         // In the dictionary.  Is it an IMMEDIATE codeword?
1761         mov %eax,%edi           // %edi = dictionary entry
1762         movb 4(%edi),%al        // Get name+flags.
1763         push %ax                // Just save it for now.
1764         call _TCFA              // Convert dictionary entry (in %edi) to codeword pointer.
1765         pop %ax
1766         andb $F_IMMED,%al       // Is IMMED flag set?
1767         mov %edi,%eax
1768         jnz 4f                  // If IMMED, jump straight to executing.
1769
1770         jmp 2f
1771
1772 1:      // Not in the dictionary (not a word) so assume it's a literal number.
1773         incl interpret_is_lit
1774         call _SNUMBER           // Returns the parsed number in %eax
1775         mov %eax,%ebx
1776         mov $LIT,%eax           // The word is LIT
1777
1778 2:      // Are we compiling or executing?
1779         movl var_STATE,%edx
1780         test %edx,%edx
1781         jz 4f                   // Jump if executing.
1782
1783         // Compiling - just append the word to the current dictionary definition.
1784         call _COMMA
1785         mov interpret_is_lit,%ecx // Was it a literal?
1786         test %ecx,%ecx
1787         jz 3f
1788         mov %ebx,%eax           // Yes, so LIT is followed by a number.
1789         call _COMMA
1790 3:      NEXT
1791
1792 4:      // Executing - run it!
1793         mov interpret_is_lit,%ecx // Literal?
1794         test %ecx,%ecx          // Literal?
1795         jnz 5f
1796
1797         // Not a literal, execute it now.  This never returns, but the codeword will
1798         // eventually call NEXT which will reenter the loop in INTERPRETER.
1799         jmp *(%eax)
1800
1801 5:      // Executing a literal, which means push it on the stack.
1802         push %ebx
1803         NEXT
1804
1805         .data
1806         .align 4
1807 interpret_is_lit:
1808         .int 0                  // Flag used to record if reading a literal
1809
1810 /*
1811         ODDS AND ENDS ----------------------------------------------------------------------
1812
1813         CHAR puts the ASCII code of the first character of the following word on the stack.  For example
1814         CHAR A puts 65 on the stack.
1815
1816         SYSEXIT pops the status off the stack and exits the process (using Linux exit syscall).
1817 */
1818
1819         defcode "CHAR",4,,CHAR
1820         call _WORD              // Returns %ecx = length, %edi = pointer to word.
1821         xor %eax,%eax
1822         movb (%edi),%al         // Get the first character of the word.
1823         push %eax               // Push it onto the stack.
1824         NEXT
1825
1826         // NB: SYSEXIT must be the last entry in the built-in dictionary.
1827         defcode SYSEXIT,7,,SYSEXIT
1828         pop %ebx
1829         mov $__NR_exit,%eax
1830         int $0x80
1831
1832 /*
1833         START OF FORTH CODE ----------------------------------------------------------------------
1834
1835         We've now reached the stage where the FORTH system is running and self-hosting.  All further
1836         words can be written as FORTH itself, including words like IF, THEN, .", etc which in most
1837         languages would be considered rather fundamental.
1838
1839         As a kind of trick, I prefill the input buffer with the initial FORTH code.  Once this code
1840         has run (when we get to the "OK" prompt), this input buffer is reused for reading any further
1841         user input.
1842
1843         Some notes about the code:
1844
1845         \ (backslash) is the FORTH way to start a comment which goes up to the next newline.  However
1846         because this is a C-style string, I have to escape the backslash, which is why they appear as
1847         \\ comment.
1848
1849         Similarly, any backslashes in the code are doubled, and " becomes \" (eg. the definition of ."
1850         is written as : .\" ... ;)
1851
1852         I use indenting to show structure.  The amount of whitespace has no meaning to FORTH however
1853         except that you must use at least one whitespace character between words, and words themselves
1854         cannot contain whitespace.
1855
1856         FORTH is case-sensitive.  Use capslock!
1857
1858         Enjoy!
1859 */
1860
1861         .data
1862         .align 4096
1863 buffer:
1864         // Multi-line constant gives 'Warning: unterminated string; newline inserted' messages which you can ignore
1865         .ascii "\
1866 \\ Define some character constants
1867 : '\\n'   10 ;
1868 : 'SPACE' 32 ;
1869 : '\"'    34 ;
1870 : ':'     58 ;
1871
1872 \\ CR prints a carriage return
1873 : CR '\\n' EMIT ;
1874
1875 \\ SPACE prints a space
1876 : SPACE 'SPACE' EMIT ;
1877
1878 \\ Primitive . (DOT) function doesn't follow with a blank, so redefine it to behave like FORTH.
1879 \\ Notice how we can trivially redefine existing functions.
1880 : . . SPACE ;
1881
1882 \\ DUP, DROP are defined in assembly for speed, but this is how you might define them
1883 \\ in FORTH.  Notice use of the scratch variables _X and _Y.
1884 \\ : DUP _X ! _X @ _X @ ;
1885 \\ : DROP _X ! ;
1886
1887 \\ The 2... versions of the standard operators work on pairs of stack entries.  They're not used
1888 \\ very commonly so not really worth writing in assembler.  Here is how they are defined in FORTH.
1889 : 2DUP OVER OVER ;
1890 : 2DROP DROP DROP ;
1891
1892 \\ More standard FORTH words.
1893 : 2* 2 * ;
1894 : 2/ 2 / ;
1895
1896 \\ [ and ] allow you to break into immediate mode while compiling a word.
1897 : [ IMMEDIATE           \\ define [ as an immediate word
1898         0 STATE !       \\ go into immediate mode
1899         ;
1900
1901 : ]
1902         1 STATE !       \\ go back to compile mode
1903         ;
1904
1905 \\ LITERAL takes whatever is on the stack and compiles LIT <foo>
1906 : LITERAL IMMEDIATE
1907         ' LIT ,         \\ compile LIT
1908         ,               \\ compile the literal itself (from the stack)
1909         ;
1910
1911 \\ condition IF true-part THEN rest
1912 \\   compiles to:
1913 \\ condition 0BRANCH OFFSET true-part rest
1914 \\   where OFFSET is the offset of 'rest'
1915 \\ condition IF true-part ELSE false-part THEN
1916 \\   compiles to:
1917 \\ condition 0BRANCH OFFSET true-part BRANCH OFFSET2 false-part rest
1918 \\   where OFFSET if the offset of false-part and OFFSET2 is the offset of rest
1919
1920 \\ IF is an IMMEDIATE word which compiles 0BRANCH followed by a dummy offset, and places
1921 \\ the address of the 0BRANCH on the stack.  Later when we see THEN, we pop that address
1922 \\ off the stack, calculate the offset, and back-fill the offset.
1923 : IF IMMEDIATE
1924         ' 0BRANCH ,     \\ compile 0BRANCH
1925         HERE @          \\ save location of the offset on the stack
1926         0 ,             \\ compile a dummy offset
1927 ;
1928
1929 : THEN IMMEDIATE
1930         DUP
1931         HERE @ SWAP -   \\ calculate the offset from the address saved on the stack
1932         SWAP !          \\ store the offset in the back-filled location
1933 ;
1934
1935 : ELSE IMMEDIATE
1936         ' BRANCH ,      \\ definite branch to just over the false-part
1937         HERE @          \\ save location of the offset on the stack
1938         0 ,             \\ compile a dummy offset
1939         SWAP            \\ now back-fill the original (IF) offset
1940         DUP             \\ same as for THEN word above
1941         HERE @ SWAP -
1942         SWAP !
1943 ;
1944
1945 \\ BEGIN loop-part condition UNTIL
1946 \\   compiles to:
1947 \\ loop-part condition 0BRANCH OFFSET
1948 \\   where OFFSET points back to the loop-part
1949 \\ This is like do { loop-part } while (condition) in the C language
1950 : BEGIN IMMEDIATE
1951         HERE @          \\ save location on the stack
1952 ;
1953
1954 : UNTIL IMMEDIATE
1955         ' 0BRANCH ,     \\ compile 0BRANCH
1956         HERE @ -        \\ calculate the offset from the address saved on the stack
1957         ,               \\ compile the offset here
1958 ;
1959
1960 \\ BEGIN loop-part AGAIN
1961 \\   compiles to:
1962 \\ loop-part BRANCH OFFSET
1963 \\   where OFFSET points back to the loop-part
1964 \\ In other words, an infinite loop which can only be returned from with EXIT
1965 : AGAIN IMMEDIATE
1966         ' BRANCH ,      \\ compile BRANCH
1967         HERE @ -        \\ calculate the offset back
1968         ,               \\ compile the offset here
1969 ;
1970
1971 \\ BEGIN condition WHILE loop-part REPEAT
1972 \\   compiles to:
1973 \\ condition 0BRANCH OFFSET2 loop-part BRANCH OFFSET
1974 \\   where OFFSET points back to condition (the beginning) and OFFSET2 points to after the whole piece of code
1975 \\ So this is like a while (condition) { loop-part } loop in the C language
1976 : WHILE IMMEDIATE
1977         ' 0BRANCH ,     \\ compile 0BRANCH
1978         HERE @          \\ save location of the offset2 on the stack
1979         0 ,             \\ compile a dummy offset2
1980 ;
1981
1982 : REPEAT IMMEDIATE
1983         ' BRANCH ,      \\ compile BRANCH
1984         SWAP            \\ get the original offset (from BEGIN)
1985         HERE @ - ,      \\ and compile it after BRANCH
1986         DUP
1987         HERE @ SWAP -   \\ calculate the offset2
1988         SWAP !          \\ and back-fill it in the original location
1989 ;
1990
1991 \\ With the looping constructs, we can now write SPACES, which writes n spaces to stdout.
1992 : SPACES
1993         BEGIN
1994                 SPACE   \\ print a space
1995                 1-      \\ until we count down to 0
1996                 DUP 0=
1997         UNTIL
1998 ;
1999
2000 \\ .S prints the contents of the stack.  Very useful for debugging.
2001 : .S
2002         DSP@            \\ get current stack pointer
2003         BEGIN
2004                 DUP @ .         \\ print the stack element
2005                 4+              \\ move up
2006                 DUP S0 @ 4- =   \\ stop when we get to the top
2007         UNTIL
2008         DROP
2009 ;
2010
2011 \\ DEPTH returns the depth of the stack.
2012 : DEPTH S0 @ DSP@ - ;
2013
2014 \\ .\" is the print string operator in FORTH.  Example: .\" Something to print\"
2015 \\ The space after the operator is the ordinary space required between words.
2016 \\ This is tricky to define because it has to do different things depending on whether
2017 \\ we are compiling or in immediate mode.  (Thus the word is marked IMMEDIATE so it can
2018 \\ detect this and do different things).
2019 \\ In immediate mode we just keep reading characters and printing them until we get to
2020 \\ the next double quote.
2021 \\ In compile mode we have the problem of where we're going to store the string (remember
2022 \\ that the input buffer where the string comes from may be overwritten by the time we
2023 \\ come round to running the function).  We store the string in the compiled function
2024 \\ like this:
2025 \\   LITSTRING, string length, string rounded up to 4 bytes, EMITSTRING, ...
2026 : .\" IMMEDIATE
2027         STATE @         \\ compiling?
2028         IF
2029                 ' LITSTRING ,   \\ compile LITSTRING
2030                 HERE @          \\ save the address of the length word on the stack
2031                 0 ,             \\ dummy length - we don't know what it is yet
2032                 BEGIN
2033                         KEY             \\ get next character of the string
2034                         DUP '\"' <>
2035                 WHILE
2036                         HERE @ !b       \\ store the character in the compiled image
2037                         1 HERE +!       \\ increment HERE pointer by 1 byte
2038                 REPEAT
2039                 DROP            \\ drop the double quote character at the end
2040                 DUP             \\ get the saved address of the length word
2041                 HERE @ SWAP -   \\ calculate the length
2042                 4-              \\ subtract 4 (because we measured from the start of the length word)
2043                 SWAP !          \\ and back-fill the length location
2044                 HERE @          \\ round up to next multiple of 4 bytes for the remaining code
2045                 3 +
2046                 3 INVERT AND
2047                 HERE !
2048                 ' EMITSTRING ,  \\ compile the final EMITSTRING
2049         ELSE
2050                 \\ In immediate mode, just read characters and print them until we get
2051                 \\ to the ending double quote.  Much simpler than the above code!
2052                 BEGIN
2053                         KEY
2054                         DUP '\"' = IF EXIT THEN
2055                         EMIT
2056                 AGAIN
2057         THEN
2058 ;
2059
2060 \\ While compiling, [COMPILE] WORD compiles WORD if it would otherwise be IMMEDIATE.
2061 : [COMPILE] IMMEDIATE
2062         WORD            \\ get the next word
2063         FIND            \\ find it in the dictionary
2064         >CFA            \\ get its codeword
2065         ,               \\ and compile that
2066 ;
2067
2068 \\ RECURSE makes a recursive call to the current word that is being compiled.
2069 \\ Normally while a word is being compiled, it is marked HIDDEN so that references to the
2070 \\ same word within are calls to the previous definition of the word.
2071 : RECURSE IMMEDIATE
2072         LATEST @ >CFA   \\ LATEST points to the word being compiled at the moment
2073         ,               \\ compile it
2074 ;
2075
2076 \\ ALLOT is used to allocate (static) memory when compiling.  It increases HERE by
2077 \\ the amount given on the stack.
2078 : ALLOT HERE +! ;
2079
2080
2081 \\ Finally print the welcome prompt.
2082 .\" OK \"
2083 "
2084
2085 _initbufftop:
2086         .align 4096
2087 buffend:
2088
2089 currkey:
2090         .int buffer
2091 bufftop:
2092         .int _initbufftop
2093
2094 /* END OF jonesforth.S */