README.md

   1 # Building and running
   2
   3 Create the executable:
   4
   5     $ make main
   6
   7 The `sys.f` file contains code that defines some of the usual words that you
   8 would expect in a Forth distribution. To run this code and then read from
   9 standard input, run:
  10
  11     $ cat sys.f - | ./main
  12
  13 The `example.f` file contains an example that you can run with:
  14
  15     $ cat sys.f example.f | ./main
  16
  17 # Notes on implementation
  18
  19 This is my summary of the most important parts of
  20 https://raw.githubusercontent.com/nornagon/jonesforth/master/jonesforth.S.
  21
  22 ## Dictionary
  23
  24 In Forth, words are stored in a dictionary. The dictionary is a linked list whose entries look like this:
  25
  26     +------------------------+--------+---------- - - - - +----------- - - - -
  27     | LINK POINTER           | LENGTH/| NAME              | DEFINITION
  28     |                        | FLAGS  |                   |
  29     +--- (4 bytes) ----------+- byte -+- n bytes  - - - - +----------- - - - -
  30
  31 For example, DOUBLE and QUADRUPLE may be stored like this:
  32
  33       pointer to previous word
  34        ^
  35        |
  36     +--|------+---+---+---+---+---+---+---+---+------------- - - - -
  37     | LINK    | 6 | D | O | U | B | L | E | 0 | (definition ...)
  38     +---------+---+---+---+---+---+---+---+---+------------- - - - -
  39        ^       len                         padding
  40        |
  41     +--|------+---+---+---+---+---+---+---+---+---+---+---+---+------------- - - - -
  42     | LINK    | 9 | Q | U | A | D | R | U | P | L | E | 0 | 0 | (definition ...)
  43     +---------+---+---+---+---+---+---+---+---+---+---+---+---+------------- - - - -
  44        ^       len                                     padding
  45        |
  46        |
  47     LATEST
  48
  49 The Forth variable LATEST contains a pointer to the most recently defined word.
  50
  51 ## Threaded code
  52
  53 In a typical Forth interpreter, code is stored in a peculiar way. (This way of
  54 storing code is primarily motivated by space contraints on early systems.)
  55
  56 The definition of a word is stored as a sequence of memory adresses of each of
  57 the words making up that definition. (At the end of a compiled definition, there
  58 is also some extra code that causes execution to continue in the correct way.)
  59
  60 We use a register (ESI) to store a reference to the next index of the
  61 word (inside a definition) that we are executing. Then, in order to execute a
  62 word, we just jump to whatever address is pointed to by ESI. The code for
  63 updating ESI and continuing execution is stored at the end of each subroutine.
  64
  65 Of course, this approach only works if each of the words that we are executing
  66 is defined in assembly, but we also want to be able to execute Forth words!
  67
  68 We get around this problem by adding a "codeword" to the beginning of any
  69 compiled subroutine. This codeword is a pointer to the intrepreter to run the
  70 given function. In order to run such functions, we actually need two jumps when
  71 executing: In order to execute a word, we jump to the address at the location
  72 pointed to by the address in ESI.
  73
  74 ## Definitions
  75
  76 What does the codeword of a Forth word contain? It needs to save the old value
  77 of ESI (so that we can resume execution of whatever outer definition we are
  78 executing at the time) and set the new version of ESI to point to the first word
  79 in the inner definition.
  80
  81 The stack where the values of ESI are stored is called the "return stack". We
  82 will use EBP for the return stack.
  83
  84 As mentioned, whenever we finish executing a Forth word, we will need to
  85 continue execution in the manner described in the previous section. When the
  86 word being executed is itself written in Forth, we need to pop the old value of
  87 ESI that we saved at the beginning of the definition before doing this.
  88
  89 Thus, the actual data for a word in a dictionary will look something like this:
  90
  91       pointer to previous word
  92        ^
  93        |
  94     +--|------+---+---+---+---+---+---+---+---+------------+------------+------------+------------+
  95     | LINK    | 6 | D | O | U | B | L | E | 0 | DOCOL      | DUP        | +          | EXIT       |
  96     +---------+---+---+---+---+---+---+---+---+------------+--|---------+------------+------------+
  97        ^       len                         pad  codeword      |
  98        |                                                      V
  99       LINK in next word                            points to codeword of DUP
 100
 101 Here, DOCOL (the codeword) is address of the simple interpreter described above,
 102 while EXIT a word (implemented in assembly) that takes care of popping ESI and
 103 continuing execution. Note that DOCOL, DUP, + and EXIT are all stored as
 104 addresses which point to codewords.
 105
 106 ## Literals
 107
 108 Literals are handled in a special way. There is a word in Forth, called LIT,
 109 implemented in assembly. When executed, this word looks at the next Forth
 110 instruction (i.e. the value of ESI), and places that on the stack as a literal,
 111 and then manipulates ESI to skip over the literal value.
 112
 113 ## Built-in variables
 114
 115 * **STATE** -- Is the interpreter executing code (0) or compiling a word (non-zero)?
 116 * **LATEST** -- Points to the latest (most recently defined) word in the dictionary.
 117 * **HERE** -- Points to the next free byte of memory.  When compiling, compiled words go here.
 118 * **S0** -- Stores the address of the top of the parameter stack.
 119 * **BASE** -- The current base for printing and reading numbers.
 120
 121 ## Input and lookup
 122
 123 `WORD` reads a word from standard input and pushes a string (in the form of an
 124 address followed by the length of the string) to the stack. (It uses an internal
 125 buffer that is overwritten each time it is called.)
 126
 127 `FIND` takes a word as parsed by `WORD` and looks it up in the dictionary. It
 128 returns the address of the dictionary header of that word if it is found.
 129 Otherwise, it returns 0.
 130
 131 `>CFA` turns a dictionary pointer into a codeword pointer. This is used when
 132 compiling.
 133
 134 ## Compilation
 135
 136 The Forth word INTERPRET runs in a loop, reading in words (with WORD), looking
 137 them up (with FIND), turning them into codeword pointers (with >CFA) and then
 138 deciding what to do with them.
 139
 140 In immediate mode (when STATE is zero), the word is simply executed immediately.
 141
 142 In compilation mode, INTERPRET appends the codeword pointer to user memory
 143 (which is at HERE). However, if a word has the immediate flag set, then it is
 144 run immediately, even in compile mode.
 145
 146 ### Definition of `:` and `;`
 147
 148 The word `:` starts by reading in the new word. Then it creates a new entry for
 149 that word in the dictoinary, updating the contents of `LATEST`, to which it
 150 appends the word `DOCOL`. Then, it switches to compile mode.
 151
 152 The word `;` simply appends `EXIT` to the currently compiling definition and
 153 then switches back to immediate mode.
 154
 155 These words rely on `,` to append words to the currently compiling definition.
 156 This word simply appends some literal value to `HERE` and moves the `HERE`
 157 pointer forward.