Dr Dobbs May 1978 - Forth for Microcomputers page 21
|
FORTH
for Microcomputers
|
|
|
BY JOHN S. JAMES 1090 Miller Ave. Berkeley, CA 94708 Forth is a unique threaded language ideally suited for microcomputers. Programs are incredibly compact; e.g. in 5K to 6K bytes you can get the interactive Forth compiler, running stand-alone as its own operating system including I/O drivers and other run-time routines, plus an assembler written in Forth (in case you want to optimize time-critical programs), virtual memory software, and a text editor. Not only does all this fit into 5K to 6K bytes (of which 4K are written in Forth), but it runs in the same space (plus 1K buffer), with no additional symbol table area, overlays, swapping, or use of any other software.
And while Forth gives all the convenience of interactive interpreters, it is very fast. For most applications, the runtime overhead is 20 to 30% for minis and 70 to 100% for micros (compared to 1000% or more which is common for interpreters). Number-crunching applications may take longer. And when Forth isn't fast enough, the system's own assembler can be used to re-code inner loops.
But the best news of all is that software development times are cut by half or more over assembly programming. The programming is entirely structured (there is no GOTO), and the resulting code is reentrant and can be designed for PROM.
Forth has been implemented on many microcomputers. A recommended configuration is 16K bytes and a terminal; a floppy is a good idea for storing source programs (and virtual memory for programs and data is supported). Forth works well with a CRT, so hard copy is less necessary.
Forth has existed for several years, and is used commercially in a number of installations, but until recently it has been priced far out of reach of hobbyists, and even most computer experts have never heard of it. However, the language is in the public domain, and today low-cost versions are just becoming available. Also there is a new Forth Interest Group (787 Old County Rd, San Carlos, CA 94070), dedicated to letting the serious hobbyist and the professional know about Forth and how they can get it. How it Works-Overview Forth is very different from any other language in common use. Perhaps the nearest is Lisp, which it resembles in one way only: both are tree-structured languages which implement themselves. Forth is an extensible, interactive language.
Forth starts with about 40 primitives, or operations defined in machine language. New operations are defined in terms of these. (So far this is like the virtual-machine systems often used for implementing transportable languages—e.g. Tiny BASIC, or P-code for Pascal. But in Forth, as soon as a new operation is defined, it can be used in further definitions or executed immediately, exactly as if it were a primitive).
|
There are no argument lists in Forth; instead, all routines (operations) communicate through a stack. The programmer is allowed to define variables, but in Forth, variables themselves are operations which place addresses (or other values) onto the stack—and which may use the full power of Forth or of machine language to compute these addresses. This means that users can create their own variable types.
Forth comes with about 140 routines already defined (including the 40 primitives mentioned above). Programming consists of defining new routines in terms of previously-defined ones, until finally one of them is the whole program which is desired. It then is executed by typing its name. Incidently, the programmer does not need to know about all 140 operations, because some of them are used mainly by the system. After all, these 140 implement the compiler, text editor, assembler, stand-alone operating system and run-time software, etc.
Execution is fast because at run time all definitions are stored as strings of addresses; and it takes as little as two instruction executions (e.g. on the PDP-11) to go from one primitive to the next. Higher levels of nesting take a little longer, but are done less often.
Debugging is exceptionally convenient because of the modularity of programs. Almost any routine can be executed by typing test-data arguments (which places their addresses or values onto the stack), then typing the name; no driver program is required. In practice, most Forth routines are very short, no more than five lines of source code, often one line. Each routine is checked out independently, then saved in an application-oriented library for future use.
Blanks are the standard delimiters, so any string of non-blank characters can be an operation name. Examples of actual names are 'ASSEMBLER', 'ELSE', '!', '(', '*', '1+'. Even numbers can be defined as operations. In one practical joke, '0' was defined as seventeen. Operation names can be encrypted with embedded non -printing characters.
Example: A Small Program Forth uses postfix notation like the Hewlett-Packard stack calculators. This means that operands are written first, followed by operators. E.g. `(A + B) * C' in regular (infix) notation becomes 'A B + C*' in postfix. This expression is executed as follows: place A onto the stack; place B onto the stack; add the two values on top of the stack, destroying both of them and placing their sum on the stack; place C onto the stack; multiply the top two values on the stack, replacing them by their product. Notice that there are no parentheses in post-fix. Also, Forth follows the convention of leaving the operands in the same order as in the infix expression; this makes it easy to remember the order of arguments for non-commutative operations like subtraction. Another Forth convention is that all operations should destroy all of their arguments on the stack.
|
Dr Dobbs May 1978 - Forth for Microcomputers page 22
|
Now let's look at a complete Forth program. Assume that the system is in the machine, but not any user programming. The task is to write a routine to evaluate the polynomial 5X2 -7X -10. The user types
: POLY DUP DUP * 5 * SWAP 7 * -10 - ;
This is the complete program. Let's follow how it works in detail.
The colon is one of the Forth operations called defining words. A defining word takes the next word in the input stream (here 'POLY), and prepares an entry for it in the dictionary of Forth definitions. As explained later, the dictionary is the most central concept in Forth. In fact, in the entire Forth system, including compiler, text editor, operating system, etc. and also the user's application software, less than 50 bytes of code are not part of the dictionary.
Besides opening a dictionary entry, the colon also places the system into compile mode, so that operations which follow are compiled into the definitions, instead of being executed immediately. It is, however, possible to have special immediate operations within definitions, when compile-time execution is desired. The system stays in compile mode until the definition is terminated by a semicolon. Notice that blanks must be used as delimiters for colon, semicolon, and all other operations.
'DUP' is an operation to duplicate the top of the stack, i.e. to push a copy of the top item onto the stack. 'SWAP' reverses the top two items on the stack, and are multiply and subtract.
For this illustration, assume that 'POLY' is executed with the argument '6' on the stack. First the '6' is duplicated twice, leaving three copies of '6' on the stack. Then multiplication is executed, leaving the stack as follows: 36
6
And '5*' pushes '5' and multiplies, leaving 5X2 (180) on top of the stack, with the copy of X beneath.
'SWAP 7*-' brings the copy of X to the top of the stack, multiplies by 7, and subtracts. '10 -' completes the polynomial.
To test the program, the user could type:
3 POLY .
where "." is the command to print the value of top of the stack
(the "." could have been included in the definition of 'POLY).
The system responds:
14 OK
where 'OK' is the prompt meaning that the system is finished and waiting for the next input. (The underline means it was typed by the system.)
The user may do some further testing:
75 POLY . 27590 OK
90 POLY . -25676 OK
Notice the overflow on the last example; the width of the stack is always 16 bits in standard Forth, although double precision or floating point can be implemented, using more than one stack entry to represent a number.
It is important to test that the routine doesn't leave anything extra on the stack, because stack overflow is not checked during execution and can be hard to diagnose. The instruction, `S, pushes the absolute machine address of the top of the stack onto the stack. This address should be the same after a test of an operation as before (provided that arguments are supplied and results printed by the test). E.g. to test 'POLY':
'S. 174 OK
8 POLY . 254 OK
'S. 174 OK
|
Example: Number Bases Any number base can be used: 'DECIMAL', 'HEX', 'OCTAL', 'BINARY', '5 BASE', '17 BASE', etc. For bases above 16, letters after 'F' in the alphabet will be used as numbers. The base can be changed at any time. Only the terminal I/O is affected - all internal work is in binary, so there is little cost for arbitrary number bases. E.g.
DECIMAL 666 23 BASE ! . DECIMAL 15M OK
This code means: make sure the system is in decimal; enter decimal 666, then 23, onto the stack; enter the address of the system's variable 'BASE' onto the stack; store (the '!' operation) 23 into 'BASE', which sets the base to 23 and destroys the address of 'BASE' and the number '23' on the stack; print 666 in base 23 (15M); and restore the base to decimal, for the sake of future definitions or data entry. By convention, the standard base is decimal. Example: Scaling Software floating point has seldom been implemented in microcomputer Forth until recently, and still is not available on most systems (it is more common on larger Forth versions for minicomputers). Instead, Forth has used some tricks for getting around the need for floating point, such as a special scaling operation '/*MOD (multiply and then divide, leaving quotient and remainder), which keeps a 24-bit intermediate result (instead of keeping only 16 bits as would happen if regular multiply and divide operations were used). So powerful are these special operations that Forth without floating point has been used for such applications as non-linear least squares, Fourier transforms, and numerical integration.
For this example, we want a program to multiply a number by 3.14159. The challenge is that we are working in fixed point, using 16-bit signed numbers with maximum value of 32,767. Also, the division operation in this version of Forth only allows divisors up to 128.
Although it doesn't make much difference in this short example, the Forth programmer is strongly advised to start with a top-down approach, taking the whole task and breaking it into operations which could implement the entire job in a couple lines of code, then breaking down these operations, etc. The alternative is to start out defining operations which seem to be relevant to the applications, but may not turn out to be useful. Don't be tempted down the wrong path by the fact that the lower-level operations must be typed in first.
In this case we can break up the task of scaling by a six-digit number (which would not even fit into a word) into three scalings by two digits each. We notice that divisions are by 100, which is allowed, and that no intermediate results on the stack will be any larger than the answer, avoiding overflow problems. The final program becomes: : FIRSTSCALE 31 10 */ ;
: NEXTSCALE 41 100 */ 10 / ;
: LASTSCALE 59 100 */ 100 / 10 / ;
: PI DUP FIRSTSCALE OVER NEXTSCALE + SWAP LASTSCALE + ; Now the user can type: 10000 PI . 31415 OK or use PI in other definitions.
The 'OVER' operation copies the second element on the stack without destroying it and pushes the copy onto the stack. The scaling operation '*/' is like '*/MOD', except that only the quotient, not the remainder, is returned.
|
Dr Dobbs May 1978 - Forth for Microcomputers page 23
|
The reader can follow through this example. Typing, e.g., '10000 PI .' first pushes 10000 onto the stack, then executes 'PI'. 'Pl' duplicates the stack, then executes 'FIRSTSCALE', which pushes 31, then 10, then executes the scaling operation which multiplies 10000 by 31 (keeping 24 bits for the result), then divides by 10, returning a 16-bit result. Now the stack is:
31000
10000
and execution continues with 'OVER', 'NEXTSCALE', '+', etc;
For efficiency, this example could be improved by first translating 3.14159 to octal or hex, then using Forth's assembler to write a divide-by -shifting routine, as the standard divide software is not smart enough to recognize that a divisor is a power of two. However, run-time speed would not be much improved by defining this program in one operation instead of four, because linkage between routines is very fast. The overhead in number-crunching applications is due more to stack manipulation than to linkage. And when time is critical, the Forth assembler is convenient.
Example: Complete Session
The 'PI' example illustrated some practical advantages of Forth for software development. It is no surprise that this program worked on the first try. Testing was immediate. The operation is now available for any further use, simply by writing its name. This routine takes about 75 bytes of object code; the compactness would be more impressive it were part of an applications package in which references to 'PI', which take two bytes, were used a few times.
The following listing shows the same example, but in a complete terminal session including use of the editor. This session starts after the Forth system has been loaded. Loading the system takes about 30 seconds on the 6502; this includes compilation of all but the first 2K bytes, which must be pre-compiled because it includes operations necessary for the system to perform compilation. The rest of the system code is left in source form, to allow user modifications. Because compilation is fast, there is no need to store object code on disk, hence no need for relocation. While overlays can be defined, Forth is so compact that they are seldom needed.
42 LIST
SCR # 42
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
OK
EDITOR OK
0 P ( MULTIPLE BY 3.14159 ) OK
1 P : FIRSTSCALE 31 10 */ ; OK
2 P : NEXTSCALE 41 100 */ 10 / ; OK
3 P : LASTSCALE 59 100 */ 100 / 10 / ; OK
4 P : PI DUP FIRSTSCALE OVER NEXTSCALE +
SWAP LASTSCALE + ; OK
42 LOAD 0K
10000 PI . 31415 OK
'S . 176 OK
45 PI . 140 UK
'S . 176 OK
The user listed a disk screen (here number 42) to confirm that it was empty. Then the word 'EDITOR' invoked the editor vocabulary.
|
This does not load the editor, which is compact enough to normally reside in RAM (though it can be loaded when used, if memory is tight). Instead, 'EDITOR' caused the editor operations to be recognized.
The program is typed using the editor's 'P' command, which places the new line being typed into the line number given, destroying whatever may have been in that line before. There are several other editor commands not shown here. This is a line editor, and cannot modify within a line. A more sophisticated string editor has been developed.
'42 LOAD' causes the disk screen to be input just as if the information had been typed; this causes the compilation to be performed. Some tests of 'PI' are shown. The answer is correct (though not rounded in the last place); and the operation does' not leave anything extra on the stack, or take anything away except its argument. Example: Using the Assembler To invoke the assembler, begin a definition with 'CODE'
instead of The manufacturer's mnemonics are available,
plus 'ELSE', and 'THEN' for conditional branching, and 'BEGIN', 'END' for conditional looping. These structured primitives can be nested to at least 16 levels, because a stack is used at assembly time. The assembly instructions must be entered in postfix: operand, mode indicator if any, then op code. Incidently this entire assembler as implemented in Forth takes only a few hundred bytes, mostly for storing the manufacturer's mnemonics.
An example of a code definition (for the 6502) is:
CODE DIV256 0 ,X LDA, 1 ,X STA,
0< IF, FF #LDA, ELSE, 00 # LDA, THEN,
0 ,X STA, NEXT JMP,
The operation 'DIV256' is here defined as a fast divide by 256. It is used to same way as any other operation; it is transparent to the user whether a routine is implemented in Forth or in code. For examples of use, see below.
Note that the op codes and some other names end in commas. In this version of Forth, it is conventional that operation names which actually place information into the code stream end with commas; these operations serve as the end of a phrase. The other names and numbers place values onto the stack, which the command operations will use. For example, '0<' places a value (an op code) that sets up what 'IF', will test for.
Though not used in this example, the full power of Forth is available at assembly time for computing address displacements. Use of the assembler does not enter into any special assembly or compile mode (it does invoke the assembler vocabulary so that assembly mnemonics are recognized). Therefore, all Forth operations are available for execution as normal.
The assembler's conditionals (e.g. 'IF') are simply Forth operations which are executed when typed, like any others. They are like macros, placing one or more machine-language instructions into the dictionary where the definition is being entered. Sometimes a forward branch is required (e.g. by 'IF'), and of course the address to branch to is unknown at the time. The macro simply leaves an empty space for an address or a byte count, and also puts the address of that empty space onto the stack. Later, the operation which marks the branch-to point simply takes that address off the stack, and patches in the final offset or address required. Incidently, the advanced programmer can deliberately produce non-structured control, by manipulating the stack during assembly.
Though not shown here, the assembler also has a 'BEGIN' ... 'END' looping structure, which repeats until the value on top of the stack becomes non-zero (true).
The following session entered and tested the definition of 'DIV256'.
|
Dr Dobbs May 1978 - Forth for Microcomputers page 24
EDITOR OK 0 P ( ASSEMBLER EXAMPLE ) OK 1 P HEX OK 2 P CODE DIV256 0 ,X LDA, 1 ,X STA, OK 3 P 0 < IF, FF # LDA, ELSE, 00 # LDA, THEN, OK 4 P 0 ,A STA NEXT JMP, OK FLUSH OK 43 LOAD STA ? EDITOR OK SCR ? 43 OK 4 P 0 ,X STA NEXT JMP, OK FLUSH OK 43 LOAD OK 77 DIV256 . 0 OK 300 DIV256 . 3 OK DECIMAL OK 77 DIV256 . DIV ? 77 DIV256 . 0 OK 400 DIV256 . 1 OK 10000 DIV256 . 39 OK -300 DIV256 . -2 OK -3 DIV256 . -1 OK -256 DIV256 . -1 OK -257 DIV256 . -2 OK |
This session has some errors; e.g. in the sixth line, 'STA' has the comma omitted. The error message 'STA ?' was printed in the eighth line. In the seventeenth line, mistyping the operation name caused 'DIV' to be unrecognized. Notice that 'HEX' stayed in effect after the code entry, until the 'DECIMAL' operation in line 16. Also, all quotients are truncated downward, even negative quotients, e.g. '-3 DIV256 . -1 OK' 'FLUSH' writes the updated buffers to disk, making sure that the copy of the program is actually saved. 'SCR .' places the address of the system's variable 'SCR', which holds the number of the disk screen being worked on, onto the stack, then '?' takes the address off the top of the stack, and prints the quantity at that address.
Example, LIFE
The following Life program was contributed by Dave Boulton, of Quesnoy Corp. Object code is 475 bytes; Forth works better for larger programs where application-oriented libraries can be developed. This program took an hour and a half to write and five minutes to debug. It runs slowly, and could be speeded up by re-coding the two levels of inner loop in assembly.
|
100 LIST 101 LIST 0 ( THE GAME OF LIFE ) FORTH DEFINITIONS FORGET TASK : TASK ; 1 81 CONSTANT XLEN 25 CONSTANT YLEN 2 XLEN 1 - YLEN 1 - ARRAY UNIVERSE 3 : CEECK DUP 3 = IF DROP 2+ 4 ELSE 2 = NOT 5 IF 4 + THEN THEN ; 6 7 : CLEAR YLEN 0 DO XLEN 0 DO 0 I J UNIVERSE C! LOOP LOOP ; 8 : SET SWAP UNIVERSE 1 SWAP C! ; 9 : RESET SWAP UNIVERSE 0 SWAP C! ; 10 11 : DISPLAY HOMEUP XLEN 0 DO [ _] LOOP CR 12 YLEN 0 DO XLEN 0 DO 13 I J UNIVERSE C@ IF [ *] ELSE SPACE THEN 14 LOOP CR LOOP ; 15 101 LOAD 0 ( LIFE CONTINUED ) 1 : GENERATE YLEN 0 DO XLEN 0 DO 0 2 J 2+ YLEN MIN J 1 - 0 MAX DO 3 J 2+ XLEN MIN J 1 - 0 MAX DO 4 I J UNIVERSE C@ 1 AND + 5 LOOP LOOP 6 I J UNIVERSE C@ 1 AND SWAP OVER - ? CHECK I J UNIVERSE C! LOOP LOOP ; 8 9 : NORMALIZE YLEN 0 DO XLEN 0 DO 10 I J UNIVERSE DUP C@ DUP 3 > 11 IF DROP 0 ELSE DUP 1 > 12 IF DROP 1 THEN THEN SWAP C! 13 LOOP LOOP ; 14 : SIZE 1+ 81 MIN ['] XLEN ! 1+ 25 MIN ['] YLEN ! ; 15 : GENERATIONS 0 DO DISPLAY GENERATE NORMALIZE LOOP DISPLAY ; OK |
|
Dr Dobbs May 1978 - Forth for Microcomputers page 25
|
Instead of giving a total explanation of this program, which would expand this article into a language manual, we will sketch how it works and browse some of the mysteries.
The program is on two screens, numbers 100 and 101. The first line lists them both. Each screen has line numbers 0 through 15. By convention, line 0 contains a comment describing the screen.
Forth comments are enclosed in parentheses. The left parenthesis must be surrounded by blanks. The right parenthesis need not be preceded by a blank, though by convention it usually is. The reason for this asymmetry is that the left parenthesis is a Forth operation which causes an arbitrary character string to be skipped until a right parenthesis, which is a delimiter, if found.
The 'GENERATIONS' definition, screen 101 line 15, is the main loop of the program. It contains a 'DO' ... 'LOOP'. 'DO' takes two arguments from the stack, the initial value from the top, and a termination value below it. Looping stops one short of the termination value; e.g. '15 0 DO ... LOOP' loops 15 times, with the index going from 0 through 14. Arbitrary computation of looping parameters is of course allowed, since 'DO' doesn't care how its arguments got on the stack.
It may seem strange to have the loop termination value before the initialization, the reverse order from BASIC and others. But this way you can say, e.g., '15 GENERATIONS', which puts 15 on the stack and executes 'GENERATIONS', which puts 0 on the stack and executes 'DO'. We more often want to pass a termination value than an initialization value to a routine.
The Forth operation 'I' places onto the stack the current value of the index of the innermost 'DO' loop. This leads to a very strange fact in lines 2 and 3 of screen 101: T refers to different 'DO' loops in the two lines, because the 'DO' at the end of line 2 has changed the level of nesting.
ALEN I -YLEN 1-ARRAY UNIVERSE' creates an array named 'UNIVERSE', or dimensions 80 by 24 because XLEN and YLEN were created with values 81 and 25 in the preceding line. Notice that these statements are outside of any colon definition; they are executed immediately when typed, at "compile time" (although it is "run time" for the 'CONSTANT' and 'ARRAY' defining words). In Forth, compile time and run time are definitely separated yet very much interspersed).
'I J UNIVERSE C@ places the values of 'I' and 'J' on the stack, then executes 'UNIVERSE', which is an 80 by 24 byte array, but is also an operation. 'UNIVERSE' takes two index values from the stack, and returns the address of the selected byte. Then 'C@' takes whatever address is on top of the stack, and replaces it by the value of the byte at that address (in the low-order eight bits of the 16-bit top of the stack). Hence constructions like:
I J UNIVERSE C@ 1 AND +
which takes the I, J byte, logically ANDs it's value with 1, and adds the result to the top of the stack. That is, it increments a counter (on the stack) if the addressed byte has a '1' in its low-order bit. This statement is counting how many are alive in the three by three square surrounding the character in question. The character itself is counted, though it should not be, so it is subtracted out by line six of screen 101. Line 14, screen 101, is an optional operation to allow the size of the array to be changed but never to go over 80 by 24. The operation '[']' gets the address of whatever follows it (in this case the constant ALEN' or 'YLEN'). Later, '!' stores the second item on the stack into the address on top of the stack. In other words, this line changes the values of "constants" 'ALEN' and 'YLEN'. Operations like '[']' are mainly intended for use in implementing the Forth system, but they are available to the applications programmer.
|
Incidently, the 'ARRAY' operation (which created 'UNIVERSE') was itself defined by the programmer in two lines of code not shown here. 'ARRAY' is an example of a user-defined variable type. The full power of Forth is available to specify what happens at compile time (e.g. allocate space for the variable, if a static variable is wanted), and at run time (e.g. compute an address in the array, given subscripts).
One more operation which should be explained is 'IF' ... 'ELSE' ... 'THEN', e.g. in line 13 of screen 100,
I J UNIVERSE C@ IF [ *] ELSE SPACE THEN
The 'IF' operation takes one argument off the stack. If it is non-zero (true), the phrase after the `IF' is executed; it is zero (false), the phrase after the 'ELSE' is executed, if there is an 'ELSE' phrase. In either case, control resumes after the 'THEN'. This line takes a character from the array, and if it is non-zero prints an asterisk (left bracket introduces a literal string to be printed, and seeks a right bracket as delimiter), or if the character is zero prints a space.
Forth is not difficult - as this condensed description may make it seem. Just unusual.
How it Works - Internals
We don't know of any implementation documents. This section is a sketch in that direction.
The basic structure of Forth is simple. The difficult part of the language design is the selection of operations such that the language is able to implement itself gracefully. And the coding of the Forth system operations can be very dense. At this point we are concerned with the structure of the system, not the semantics of the particular operations. For a fuller description of the language itself, see the Decus manual (reference in bibliography), which to our knowledge is the most complete documentation readily available today. For a fuller description of the internals and implementation, check future publications of the Forth Interest Group, 787 Old County Rd., San Carlos, CA 94070.
The central structure of Forth is the dictionary. Every operation, primitive or defined, has an entry in the dictionary. All applications software, and virtually all of the Forth system, consist of dictionary entries. Of the 5K to 6K bytes of a typical microcomputer Forth system, only about 50 bytes are not part of a dictionary entry.
All dictionary entries have the same format. In most Forth systems, the first four bytes identify the word; the total length of the word, and the first three characters, are saved. Operation names may have any length; but if they have the first three characters and length the same, they will not be distinguished. This system works quite well, and confusion is rare.
Besides the length, the first byte also has a precedence bit, which tells whether the operation is immediate or not. Immediate operations are executed even when the system is in compile mode, and usually act as compiler directives or macros. Compile mode is set by the colon, and cleared by the semicolon.
The next two bytes have the link address. This is simply a pointer to the previous dictionary entry. Its purpose is to allow the dictionary to be searched, at compile time.
The next two bytes are the code address. This address is fundamental. It always points to machine code. In a code operation (either a primitive, or a user-defined assembler routine) it points to the code which implements the operation; this code begins immediately after the code pointer. In a colon definition (i.e. a standard Forth statement), it points to code which controls nesting at run time, described below. In a variable, the situation is more complicated. In this case, the code address points to
|
Dr Dobbs May 1978 - Forth for Microcomputers page 26
|
code in the dictionary entry of a defining word -a kind of operation which (a) when used at compile time makes a new entry in the dictionary, and (b) contains code which is unique to that particular class or type of variable, and which is executed at run time. The eight bytes described above form the header of the dictionary entry which defines any Forth operation—code routine, colon definition, or variable. The body of the dictionary entry consists either of machine language, a list of addresses of previously -defined operations (which may have literals interspersed, each preceded by the address of a literal-handling routine), or the value or address of the variable, array, etc., respectively.
Now we know what the dictionary looks like, for it is nothing more than a string of these dictionary entries. And the. dictionary makes up virtually all of Forth - the compiler, assembler, operating system, and all application software written by the user. Only about 50 bytes of code are outside of the dictionary. This little bit of code, known as the inner interpreter, is the heart of the system.
At run time, all operation names have been replaced by the addresses of their dictionary entries, so the inner interpreter works with addresses only, and never has to search the dictionary. The inner interpreter uses a pointer, 'I', to the next address in a definition to be executed. If possible, 'I' will be kept in a register, because the inner interpreter must be ultra fast.
Consider a particular dictionary entry for a Forth definition, and assume that one of the operation addresses in its body is just finished being executed. 'I' now points to that address in the dictionary entry.
If the routine which is finishing is a code routine (primitive or user-defined), it will end with a machine-language branch to the location 'NEXT' in the inner interpreter. There, code will increment the 'I' pointer by two, leaving it pointing to the dictionary entry of the next operation to be executed. By an indirect fetch from 'I', the code address of this new entry is moved into another pointer called 'W'. Then the inner interpreter branches indirectly to 'W'; i.e., it branches to the code address of the next routine to be executed; the code address always points to machine code. This linkage process takes as little as two instructions on minis and eight or so instructions on eight - bit micros.
This is the linkage from one code routine to another. If the new routine is not code but is a Forth definition instead, then the code address in its dictionary header points to code which handles the nesting by pushing 'I' onto the return stack, then setting 'I' from 'W' to point to the address just before the body of the Forth definition, then branching to 'NEXT'. Similarly, when the Forth definition ends, the semicolon operation points to code which pops the return stack into 'I' (removing the last level of nesting), then branches to 'NEXT'. There is also some auxiliary code for performing stack operations and then falling directly through into 'NEXT', for efficiency.
This completes the description of the inner interpreter and of the nested execution of Forth operations. This linkage happens at all times—compilation, assembly, editing, or execution of applications software. In fact there is no fundamental distinction between these times, as the whole Forth system, including the user's application software, is one unit. Miscellaneous Features Multitasking Forth is well suited to multitasking, which has been implemented on minis (though not as of now on micros). E.g. a Nova 2 (35K words) has handled up to 32 terminal users simultaneously. To switch users, only four pointers have to be changed.
|
Each user has a private vocabulary, in addition to the common vocabulary. Communication between users is accomplished by simply leaving messages in agreed-upon places.
Also on minis, a data base management system has been implemented as a Forth superset. Disk Management Virtual-memory software is standard for both micros and minis. Data is read and written in 128-byte blocks. The editor addresses 8-block (1K) units, which are called screens because they fill 16 lines of 64 characters each on a CRT. (A CRT used on a Forth system should be able to display 16 lines of 64 characters.)
The system should have memory room for at least 8 block buffers, so that a whole screen can be displayed; the same buffers are also used for applications and disk I/O. Programs request blocks by number, without regard to whether they are in memory or must be brought in from disk; the system checks whether the block is in a buffer already, reads it from the disk if not, and returns the memory address of the block on the stack. Programs can use the 'UPDATE' command to mark a block as changed; it will be written to disk before that buffer is re-used. 'FLUSH' will write all updated buffers which are currently in memory.
The system treats input identically, whether it comes from the disk or is typed in. This allows use of 'load screens', which contain commands to load other screens, so that the system and/or applications programs can be loaded automatically.
Dictionary ManagementForth is hard to categorize as interpreter, assembler or compiler, and some have even questioned whether it is a language. Whenever a character string is typed into Forth, it is first looked up in the dictionary. Only the first three characters (five in some Forth versions) and total name length are used for the match. If the name is not in the dictionary, the system tries to make a number out of it, using the number base which is currently in effect; if that cannot be done, an error message is issued. Forth operations must be defined before they are used.
It is OK to re-define a name which is already in the dictionary. Later uses of the name refer to the new definition, but earlier uses continue to refer to the old one (these earlier references have already been compiled). This means that there is no worry about accidental re-using a name, unless the old meaning must be used again the same program. Therefore the programmer can freely make use of temporary names in building up the definitions of new operations, without worrying about later conflicts.
For convenience, it is possible to 'JOIN' non-adjacent definitions, taking all intermediate definitions out of the dictionary search path.
There is also a 'FORGET' command, to wipe out the most recent dictionary entries. It is used to clear away recent scratch work. Care is advised. Forth allows you to 'FORGET' the entire system.
But the most powerful form of dictionary management is the use of vocabularies. Each vocabulary is a separate linked list of dictionary entries. Vocabularies are used to control the order of dictionary search. There is an 'ASSEMBLER' vocabulary which contains the op codes, etc; and 'EDITOR' vocabulary contains text editor commands. Also, users may define their own application vocabularies. All vocabularies link into the 'FORTH' vocabulary, which is the root of the vocabulary tree. In other words, if an operation name is not found in whichever special vocabulary is in effect, the 'FORTH' vocabulary will be searched. Users can define sub-vocabularies which similarly link into each other.
Vocabularies are implemented by the link pointers in the dictionary entries. In addition, each vocabulary has a
|
Dr Dobbs May 1978 - Forth for Microcomputers page 27
|
dictionary entry in its root vocabulary; this entry associates the vocabulary's names with a pointer to its last dictionary entry.
At any time, two vocabularies are in effect: 'CONTEXT' and 'CURRENT'. 'CONTEXT' works as described above, determining the path of dictionary search. 'CURRENT' tells which vocabulary new definitions will be linked into. If all this gets confusing, keep in mind that in any Forth system there is only one dictionary, but there may be many vocabularies. Further discussion of vocabularies is beyond the scope of this article. Microcode There is much interest in microcode implementation of Forth. One approach is to microcode only the inner interpreter. At most this could double the speed on micros and less on minis, so it would probably be more practical to use a faster chip instead.
The other approach is to microcode all 40 or so of the primitives, plus a few other operations for completeness (as there would be no "machine language" to drop out of "Forth" into). Such a machine would be many times faster. While work is proceeding, we don't know of anyone who has done it yet.
Transportability Forth is easy to move to new machines, because only 1K bytes must be re - written. An experienced implementer can do it in a few weeks. Some care must be used when transporting higher-level definitions to machines of a different architecture - e.g. when going between high-order vs. low-order byte first, character arrays may need attention.
Cross-compilation is possible, but complicated because Forth operations need two definitions, a separate one for the target machine.
Complex vocabulary manipulations are used to keep the two sets of definitions separate. Cross-compilation is commonly used when the target machine is the same chip, but to run without a terminal and perhaps from ROM, e.g. for control applications. In this case the purpose is to compress the program by eliminating those primitives and definitions which are only used by the compiler, and to shorten the remaining definitions by removing the name characters and the link pointer (which are only needed during compilation). History and Availability Forth was developed by Charles H. Moore around 1970, at the National Radio Astronomy Observatory, and to our knowledge was first described in publication in 19731. Later Mr. Moore left the NRAO and is now marketing the language through Forth, Inc., 815 Manhattan Ave., Manhattan Beach, CA 90266. The price is $10,000 for the larger, minicomputer timesharing version, including on-site training. The microcomputer version is $2,500, sent by mail and including telephone consulting. A "primer" is available separately at nominal cost. As of May 1977, Forth Inc. offered implementations on the COSMAC, 8080, 6800, Z-80, and LSI-11.
A version of Forth for the PDP-11 is available through DEC Users' Society, 126 Parker St., Maynard, MA 01754. Distribution charge is $60 for tape, or $23 for floppy. It runs under RT-11 or stand-along, and needs 8K. PDP-11 Forth is DECUS No. 11-232.
The DECUS manual is sold separately, for $2. This is the only manual we know which is readily available to the public at this time.
Also on the 11, Doug Faunt, PO 60116, Sunnyvale, CA 94088, or phone (415) 494-7030, will soon be publishing the LSI-11 Newsletter, can supply a DECUS floppy version in exchange for a floppy and return envelope.
|
For CP/M, a Forth version called STOIC is available from the CP/M Users Group, 164 W. 83rd St., New York, NY 10024. STOIC is Vol. #23, and the distribution charge is $8. Documentation is on the floppy.
The STOIC system takes about 13K for its basic definition and assembler; why is it so much larger than other systems? Several K are used for buffers to interface CP/M; and the first five characters of each name, instead of three, are saved in each dictionary definition. Also there are many more operations than in the smaller system, such as a more complete signed and unsigned arithmetic. STOIC also has additional packages for vector and matrix operations, double precision, and floating point.
Forth versions are running at various universities and research institutions; Rather and Moore 7 list three where it is available. Also, University of Rochester and University of Arizona have implementations on Varian 620-I, CDC 6600, PDP-11, and IBM370. We don't know about distribution arrangements.
For the Z-80, the Digital Group, PO 6528, Denver, CO 80206, has announced CONVERS, its version of Forth, to sell for $26, with the manual selling separately for $10, creditable toward purchase. However, the product is not yet out.
For the Alpha Micro, a version is being developed by Alpha Micro Systems, 17875 N. Sky Park, Suite N, Irvine, CA 92714.
Programme Consultants, 3400 Wilshire Blvd., Los Angeles, CA 90010, is developing Forth versions for the 6800, 6502 machines (Apple, PET, OSI), and other micros. These are intended to run without floppies.
A newly formed Forth Interest Group, 787 Old County Rd., San Carlos, CA 94070, is an information clearinghouse on the language; it does not have a version for distribution at this time. Summary Only recently have sophisticated programming languages become available for home computers and small development systems. There are others besides Forth, such as Pascal, or C. Probably each has certain applications which it can do best. Forth is very different from anything else. It is remarkable that so rich a language, which is also a stand-alone operating system, can be implemented with 6K bytes.
Software development times can be greatly reduced, especially for large projects. Rather and Moore' give as example a radio telescope control and data analysis system, including on -line interactive graphics, which they claim would typically be estimated at six man years and with 64K of memory required. It was implemented in Forth in 24 man weeks and 16K.
1. Moore, C.H., and E.D. Rather, "The FORTH program for spectral line observing," Proc. IEEE, vol. 61, September, 1973, pp. 1346 - 1349.
2. --, "FORTH: A new way to program a minicomputer," Astron. Astrophys. Suppl. 15 1974, pp. 497-511. 3. DECUS, Forth Programming System for the PDP-11, DECUS No. 11-232, September 1975. (Note also manual for the PDP-10.) 4. Stein, P., "The FORTH dimension: Mini language has many faces," Computer Decisions, November, 1975, pp. 10. 5. Rather, E.D., and C.H. Moore, "FORTH high-level programming technique on microprocessors." Presented at Electro/76 Professional Program (paper 23/4), Boston, MA, 11-14 May 1976. 6. Sinclair, W.S., "Forth: A Stack Oriented Language," Interface Age, September 1976. 7. --, "The FORTH approach to operating systems," ACM '76 Proc., pp. 233-240, October 1976. 8. Forth, Inc., Micro forth Primer, December 1976. 9. --, "The use of 'FORTH' in process control." Presented at International '77 Mini-Micro Computer Conference, Geneva, 26 May 1977. |
