Jupiter Ace Resource Site - Mastering the Forth Stack from Personal Computer News November 1983

In 1979, the Forth Interest Group (FIG) was formed to promote the use of the language and it has since then been the strictest enforcer of proper Forth implementations on home micros. Forth aficionados tend to look for the FIG seal of approval before using an implementation of the language. This standard is known as FIG-Forth and is embodied by the FIG-Forth installation manual as written by William Ragsdale.

The European Forth Users Group (EFUG) was founded in 1976, and the Forth standards team was subsequently formed in an effort to achieve a standard. This standard was finally arrived at in 1979 and has thus become known as Forth-79.

FIG-Forth and Forth-79 each have a certain following in the programming community, and no-one has yet come out with the definitive argument as to why one must be selected over the other. This is a friendly academic rivalry, however, and both FIG-Forth and Forth-79 manuals can be obtained from FIG.

MASTERING THE
FORTH STACK

W

hile the stack forms the hub of all data manipulation within Forth, the lifetime of data on the stack tends to be short. It is a convenient and reliable place to leave parameters for Forth words, but to save a build-up of data, it is common practice to have a word destroy its own parameters and merely leave the result, if any, on the stack.

The stack manipulation words are used when multiple copies of the parameters are required for successive operations, or to tidy up when surplus results have been generated. Data which needs to be stored for longer periods is normally elsewhere in memory, often in a named data area.

Two fundamental data structures come built in to any Forth system. Constants are given a value when defined and executed so as to place that value on top of the stack, thus:

1024 CONSTANT 1K (n . . .)

creates a constant named 1K that contains the 16-bit value 1024. On naming 1K either interactively or within a colon definition, the value of 1K will be placed on the stack. As the name suggests,constants are used to hold data which is relatively unchanging, since there is no obvious way of altering their value while a program is running (there are ways). For more temporary data Forth provides variables.

These may be defined to the compiler as follows:

VARIABLE TOTAL in Poly-Forth
or 0 VARIABLE TOTAL in Fig-Forth

Some dialects require an initial value on the stack at compile time, others can do without. Variables execute differently to CONSTANTS. When named within a program they provide the address where a value may be found, so you soon proceed to tamper with the contents.

TOTAL ( . . addr)

Data retrieval is performed using the word (fetch) TOTAL A ( . . . n)
while storing data uses! (store)
5 TOTAL !.)

On top of these two a further word +! is provided to take care of an extremely common operation, that of adding a value to the contents of an address. The phrase to add 3 to the contents of TOTAL might be:

TOTAL DUP A 3 + SWAP!

but using +! it becomes:

3 TOTAL +!

Since Forth performs signed arithmetic +! may also be used to decrement variables by using a negative number as an argument. So to decrement by one:

-1 TOTAL +!

The words 2, !, and +! provide a means to communicate between the stack and other parts

MEETING THE
CONDITIONS

Forth offers a fairly comprehensive selection of program structures to control the flow of conditional and interactive execution. As with other aspects of the language, any that don't come as standard can be added to specification, although this is not often done. To understand the operation of these structures it is necessary to look at the various conditional tests which can be performed.

As an example consider =, this is not the assignment statement of other languages. ie TOTAL = 0 or TOTAL = TOTAL + 1. These operations are handled by ! and +!. In Forth = takes two numbers from the stack, tests to see if they are equal, if they are a 1 is returned, otherwise a 0. The logic of Forth is such that a zero value is treated as a false flag and a non-zero value as a true flag. The full set of conditional tests with their stack inputs and outputs are shown in Figure 1.

Flags may be combined in order to produce more complex conditional tests using the logical operators shown in Figure 2. For example, to test if a number falls within a given range inclusive of the limits

These could then be used. for instance, to test if a value was as ASCII numeral

(Char. . : NUM? 48 57 WITHIN ; true if ASCII numeral

The flags produced by these conditional tests are used by the control structures to determine the path of execution. The simplest form is the IF . . . then clause. IF removes one value from the stack, and if that value is true then execution is allowed to continue in line. If it is false however execution is rerouted to code following the THEN, for example in adding up the number of under-aged drinkers in a pub the phrase:

AGE @ 18 IF 1 TOTAL + ! THEN

might be used to increment the total only if the value found in AGE was less than 18.

Optional for inclusion with IF and THEN is an ELSE statement. It is used to define code that will be executed if IF encounters a false condition, for instance counting people according to sex:

MALE?
IF 1 MEN +!
ELSE 1 WOMEN +!
THEN

If the result of MALE? is true then execution continues from ELSE or THEN. whichever comes first.

IF ELSE THEN structures may be nested to any depth :

AGE @ 18 IF MALE?
IF 1 MEN+1!
ELSE 1 WOMEN +!
THEN
THEN

to sort the under-age drinkers into two groups. The outer IF THEN could itself have had an ELSE clause to deal with the 18 and overs, and this could contain other IF THEN's.

:WITHIN

(n,lo,hi. .hi,n,n,6)
(hi,n,n,lo. .hi,n,f)
(hi,n,f. .f,n,hi)
(f,n,hi. .f,f)
(f,f. .f)
(f. .f)
or exclusive of limits
: BETWEEN
(hi,n,n,6. .hi,n f)

(f,n,hi,. .f,f)
(f,f. .f)

ROT DUP ROT
<
SWAP ROT
>
OR
NOT;

ROT DUP ROT

SWAP ROT

AND;

true if n < the low limit

true if n > the high limit
true if n outside range
reverse condition

true if n > the low limit

true if n > high limit
true if both flags true

of memory. Other words are provided to deal with byte length values and 32-bit. Movement of longer strings of data about the memory is achieved by using the stack in a different way. Instead of piling data up on the stack and then disposing of it the words MOVE and CMOVE expect to find 3 parameters on the stack, a source address, a destination address and a count for the number of data items to be moved. For instance the phrase:

HERE PAD 10 CMOVE

would move 10 bytes from HERE (the top of the dictionary) to PAD, STARTING with the 1st byte in the string. Some Versions of Forths provide the word <CMOVE which moves the last byte first to avoid overwriting data with short range moves towards high memory. If your particular Forth doesn't have one then you'll probably need to write your own.

While only two named data structures come with the Forth, others may quite readily be added due to the extendibility inherent in it. This is achieved by creating new defining words. VARIABLE and CONSTANT are known as defining words in Forth, they define a class of words which behave in the same manner when compiled and also when they execute ie all CONSTANTS remove a value from the stack during compilation, and all execute so as to place that value on the stack. The principle tools in creating new defining words are CREATE (<BUILDS in Fig-Forth) to define the way in which words will compile, and DOES> which defines the way in which they will execute.

CREATE may be used as follows:

CREATE STORE 20 ALLOT

as a compiler which creates a dictionary heading called, in this case, STORE. The ALLOT allocates 20 bytes of storage following the header. On execution STORE acts to place the address of the first byte on the stack. To use this, for example to hold an ASCII string entered from the keyboard, the phrase:

STORE 20 EXPECT

might be used, and to output to screen or printer:

STORE 20 TYPE

CREATE may also be used within a colon definition to create a class of words. For instance, if VARIABLE did not exist one way to create it would be:

:VARIABLE CREATE 2 ALLOT;defines
VARIABLE
VARIABLE COUNTER defines COUNTER
0 COUNTER ! initialize to zero

COUNTER on execution performs the runtime code for CREATE, placing the address immediately following the dictionary header on the stack, and there by doing everything expected of it. Another example would be:

:BYTES CREATE ALLOT ; (define bytes)
20 BYTES STORE (define store)
STORE 20 ERASE (initialize store)

BYTES expects a number on the stack which it uses to ALLOT dictionary space. Here a 20 byte string named STORE is created. When executed STORE also uses CREATE's behaviour pattern and leaves the start address ready for ERASE.

FORTH COMPARISONS

WORD

STACK

DESCRIPTION

=

(n, n _ _ f)

COMPARES THE TOP TWO ITEMS ON THE STACK. LEAVES A TRUE FLAG IF THEY ARE EQUAL ELSE FALSE.

<

(nf, n2 _ _ f)

COMPARES THE TOP TWO ITEMS ON THE STACK. LEAVES A TRUE FLAG IF n I IS LESS THAN n2 ELSE FALSE.

>

(n1, n2 _ _ f)

COMPARES THE TOP TWO ITEMS ON THE STACK. LEAVES A TRUE FLAG IF n I IS GREATER THAN n2 ELSE FALSE.

0=

(n _ _ f)

LEAVES A TRUE FLAG IF THE TOP ITEM ON THE STACK IS EQUAL TO ZERO, ELSE FALSE.

0<

(n _ _ f)

LEAVES A TRUE FLAG IF THE TOP ITEM ON THE STACK IS LESS THAN ZERO, ELSE FALSE.

0>

(n _ _ f)

LEAVES A TRUE FLAG IF THE TOP ITEM ON THE STACK IS GREATER THAN ZERO, ELSE FALSE.

FORTH LOGICAL OPERATIONS

WORD

STACK

DESCRIPTION

OR

(f, f _ _ f)

LEAVES A TRUE FLAG IF EITHER OF THE TOP ITEMS ON THE STACK ARE TRUE, FALSE IF THEY ARE BOTH ZERO.

AND

(f, f _ _ f)

LEAVES A TRUE FLAG IF BOTH OF THE TOP ITEMS ON THE STACK ARE TRUE, FALSE IF EITHER OF THEM ARE ZERO.

NOT

(f _ _ f)

REVERSE THE LOGICAL VALUE OF THE TOP STACK ITEM.

XOR

(f, f _ _ f)

LEAVES A TRUE FLAG IF ONLY ONE OF THE TOP TWO ITEMS ON THE STACK IS TRUE, BUT NOT IF THEY ARE BOTH TRUE (Exclusive OR)

ERASE expects a start address and byte count on the stack and clears the appropriate memory area to zero.

DOES is one of the most remarkably useful tools in the Forth system. It may only be used inside a colon definition and performs two.

functions. Consider a would-be definition for CONSTANT:

:CONSTANT CREATE , DOES> 2 ;

The phrase between CONSTANT and DOES is what CONSTANT executes. The , serves to compile a 16-bit value from the stack into the dictionary. The code for CONSTANT is terminated by DOES>. This also marks the start of the code for the word defined by CONSTANT. CREATE still leaves that address on the stack and this is used by a to push the compiled value of the constant onto the stack. The code following the DOES may be of any length and is terminated

The box labelled 'Forth Logical Operators' shows the logical operators that can be used to act on information stored in the stack, while 'Forth Comparisons' shows how various words in the Forth vocabulary compare bits of information on the stack and how they relate their findings about those bits of information.

by a semi-colon.

A more useful example of the use of DOES is the creation of arrays which take an index, as is common in most high-level languages, in this case an array of 16-bit locations suitable for single length numbers or addresses:

: ARRAY CREATE DUP , 2* ALLOT DOES 2+ swap 2+ +;

This breaks down as follows:

CREATE creates the header DUP , compiles a length cell and leaves the original number on the stack 2* ALLOT allocate twice the length number of bytes used as 10 ARRAY VALUE to create a 10 cell array called VALUES.

The code executed by VALUES follows the DOES and breaks down as follows:

(n,base-2 . . a, base) skip past the length 2+ cell
(n,base . . base, n) bring the index to the
SWAP top of the stack
(base,n . . base, compute the byte
offset) 2 offset from the base
(base,offset . . ele- compute the address
ment addr) + of the element
used as 4 VALUE to return the address of the fifth element in VALUE (note that 0 would return the first element) so that the phrase :
4 VALUE A TOTAL +!
would add it into TOTAL.

It was not necessary to incorporate the length cell in the definition of ARRAY since it only required an instruction to skip over it in the DOES> portion. It could have been put to good use though, to perform a range check on the index by modifying the DOES> code.

The section of code between DOES> and 2+ could be included in the definition of ARRAY during the development, debug and test stages of an application, and edited out of the source before final compilation in order to save dictionary space. Any words which used ARRAYS would remain unaffected by such a change since its inputs and outputs are unaltered.

Forth offers enormous scope for creating classes of objects by means of a couple of simple devices. With a little effort you can create ARRAYS with any number of dimensions, stacks and queues, or more complex objects for applications like LIST processing.

Contributors: Dick Olney and Niklos Shawl Editor: Geof Wheelwright

Design: Nigel Wingrove Illustrations: John Hallett

NEXT WEEK

We continue our look at languages in the Program Tools section of our programming course with an introduction to the Pascal programming language. And we'll also have some fun with program design when we discuss how to develop adventure games.

In the Program structure section, we take a deeper look at data structuring.

The Jupiter Ace (pictured above) is the cheapest home micro to run the Forth programming language built into it. Many other home micros, including the Sinclair ZX81, ZX Spectrum and BBC micro, will run the Forth language in cassette form.

Forth was developed by Charles H. Moore in the late 1960s as a tool to increase his productivity. In 1971, he used the language to write a data acquisition program for the National Radio Observatory at Kitt Peak, Arizona.