Finding a word in the dictionary involves more than the structure of the dictionary. The search proceeds from later to earlier entries. This is a convenient way to search since a word may be redefined and the latest definition found.
However the search does not always begin with the latest entry. To some extent this is under the user's control, but the main variation involves definitions. A definition is an entry that contains other words that must be interpreted. We specify that the search for these words begin at the defintion (Fig 5). This has 2 desirable effets: Words must be defined before they are used - a valuable diagnostic aid. And when a word is redefined, though its old meaning is not directly accessible, old definitions can still reference the old meaning. The only restriction on redefinition is exactly that - that the user need no longer directly access the old meaning.
Figure 5.
Fig. 5 Dictionary search depends upon the order in which words are declared, and the context in which they are sought: Words read from the keyboard are sought from the last entry - subject to a lower limit. Words read from definition are sought before the definition. The arrows show the portion of the dictionary searched for the definition indicated in the dictionary.
The net effect of this convention is that words may be defined, redefined and referenced in a completely natural fashion. The user rarely need trouble about the search mechanism; it follows the context so closely as to seem to be aware of his intention.
Of course the redefinition ability means that there are no reserved words. In fact there are no reserved concepts. The user is completely free to redefine any aspect of FORTH he wishes. Our system definitions are available to save him trouble, and have been selected for maximum utility. But we do not force our choices upon him.
In addition to word, address and parameter parts, each entry has a link and the dictionary becomes a linked list. Since the dictionary is large, several hundred entries, search time is important. So we scramble each word to determine which of 32 chains it will be found in and then follow the links of this chain through memory (Fig. 6). Thus with 300 entries, only 5 comparisons should produce a match. This complicates the problems of deleting entries and starting the search at definitions, but the advantage is overwhelming.
Figure 6.
Dictionary showing 3 search chains
Dashes show physical order; lines show search order.
Search Proceeds:
1- Scramble word to select chain #1, #2, or #3.
2- Find last entry in chain from array of chain heads.
3- Follow links comparing word with entry.
There is a large class of words that are defined but not in the dictionary - numbers. Numbers may be placed in the dictionary, and often are. But if a number is not found, it is assumed to define itself and its value is placed on the stack.
If a word cannot be found in the dictionary and is not a number, it is undefined and in error. The scanner will type the word and return to the keyboard for input - the current input string being abandoned. The user must correct the error, restore the dictionary and restart his program.
Next Chapter
Return to the Table of Contents