In this article, Gil Filbey discusses the Stack, the Branching technique of FORTH, and gives a couple of practical examples. You can follow with pencil and paper if you don't have a computer handy.

F

orth is a high-level programming language designed for small computers. It has been in existence for some years and has a following in America, but is only just beginning to appear in Britain. The main advantages of FORTH are:

• It requires only a small amount of
       memory
• It is fast
• It lends itself naturally to structured
       programming
• It is virtually machine independent

  I propose to illustrate the use of FORTH by showing a program and what it does; then discussing how it does it. The implementation I am using is APPLEFORTH V1.5 on cassette. I also have APPLEFORTH V1.2 by Programma International, though I have not made much use of this version yet. Both these versions are also available on disc.

ogically at this point I should explain the use of the editor. FORTH has a powerful editor, but I assume that the majority reading these articles will not yet possess any version of the language; and in any case, the editor system varies from version to version. So, for the time being, I will stick to pencil and paper problems.

The stack and
how to handle it

I dealt last month with the Dictionary, which may be likened to a tool cupboard. I now want to discuss the stack which is rather like a workbench on which the materials are placed to be worked. The materials in this case are numbers.

If I type a number and hit the RETURN key this number is placed on the stack. Further numbers can be placed on the stack in the same way. There is no need to hit RETURN between each and the next, so long as a space follows each entry. Numbers are dealt with in the reverse order to their entry by the use of the dictionary words. For this reason it is called a LIFO stack (Last In First Out).

Example

1 2 + . RETURN 3

The diagram showing the state of the stack in the above operation is (E stands for empty)

FORTH provides a number of words specially for manipulating the stack.

Examples

There are some more complicated ones which I shall describe later.

These words may be combined by typing them in succession either immediately or within a colon definition.

Example

Which has the effect of duplicating the top two stack numbers.

We could write a definition

: 2DUP OVER OVER ;

The word 2DUP can be retained in the dictionary for future use. Suppose we place the numbers 1 and 2 on the stack in that order and then repeatedly operate with 2DUP +. The state of the stack after six such operations is

  It goes like this

To see these numbers, make use of the print word (a full stop) eight times in succession a t the end, and the numbers are printed out in the reverse order. The sequence is known as a Fibonacci sequence and if you want to find out more about the fascinating properties of this sequence you should read "Patterns in Nature" by Peter Stevens in the Peregrine Books series.

You cannot go far with the above sequence produced in this way without filling the stack (about 60 entries). A better way is as follows.

: FIBONACCI DUP ROT + ;

This defines the word FIBONACCI and produces a state diagram like this

After successive use of this word the stack contains only the last two terms of the sequence. If you wish to print out the sequence term by term then define FIBONACCISHOW

: FIBONACCISHOW FIBONACCI DUP . ;
    

The final DUP here is necessary because the print word will remove the top stack number but we want it still there to produce the next term in the sequence.

A Fibonacci sequence is useful for producing random numbers. We define RANDOM

: RANDOM FIBONACCI 25000 MOD ;
    

starting with a pair of seed numbers on the stack and then invoking RANDOM will produce a number between 0 and 24999. MOD is a FORTH word which causes the second stack number to be divided by the top stack number (in this case 25000, but you can choose any number you like) and the remainder only is retained. A typical state diagram would be

(For brevity I haven't shown that 25000 is placed on the stack before the command MOD is obeyed)

I may now print successive random numbers by

Should I want to print out several without a loop construct I could save time by defining R

  I might thus use a seed pair such as 1234, 2345 R R R etc. Each R producing a printed random number.

  You can see that FORTH lends itself naturally to structured programming, since each definition is short and contains words previously defined — good top down design. However, the task has so far been easy, since the only departure from straight-line programming has been the DO LOOP.

We will now develop the branching technique as used in FORTH.

The structure here is interesting and different from that used in most other highlevel languages. Here is the flow chart.

In contradistinction to other languages THEN is :

What is done next in either case

If you like the sound of it better, define

  : IFNOT ELSE ;
: IFSO IF ;

You don't have to accept the words which come with the package. You can use your own. If no action is to be taken in the ELSE (or IFNOT) case then ELSE is dropped but it is still helpful to picture the flow chart as

The word THEN is obligatory after IF. A typical TEST is the relative size of the top two numbers on the stack.

To make a problem of it we will try to define a word called ORDER which arranges the top two numbers X Y so that the top-most is smaller than the second.

The FORTH word - asks, in affect, "is X smaller than Y?"

  The test removes the numbers, however, so if we want to keep them we must write 2DUP first.

  The following defines ORDER

: ORDER 2DUP < IF SWAP THEN ; 

  The next command after THEN doesn't need stating at this stage. It will be stated by whatever word follows ORDER in the next definition

The stack state diagram

  The final result will be in the order LARGER SMALLER

  The opposite word REDRO (ORDER backwards).

: REDRO 2DUP > IF SWAP THEN ;

  I will leave it to you to show that the defined word MIDDLEDROP

: MIDDLEDROP ORDER ROT
      REDRO ROT ORDER DROP ;

will reject the middle number out of the top three on the stack leaving only the least and the greatest in that order so that a print-out of the result would give GREATEST LEAST. This will be true whatever the starting order. Show also that if there are N numbers on the stack then N-2 applications of MIDDLEDROP leaves the two extremes only on the stack at the end. They can then be printed or further used.

  Here is a print-out of the use of the word TESTS

: TESTS O DO MIDDLEDROP 2DUP . .
 1 ON LOOP ;  

OK
1 0 8 9 3 7 5 6 6 4 3 OK
CR CR 8 TESTS

6 3 6 3 6 3 7 3 7 3 9 3 9 0 9 8
OK  

It prints out the current candidates in pairs as it goes.

  We can now generate random numbers by the FIBONACCI word and sift them by the word MAXMIN

: MAXMIN 0 DO MIDDLEDROP LOOP ;   

Typical result

  1234 2345 50 RANDOMS 50 MAXMIN . .

  We can defind LOTS.

: LOTS 0 DO 50 RANDOMS
 50 MAXMIN LOOP . . ; 

1234 2345 20 LOTS

does 20 batches of 50 random numbers with each batch using the MAX and MIN of the previous batch as a starting seed. The final print-out is the GREATEST and LEAST of Random numbers.