Languages
FORTH
Gil Filbey
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:
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. |
L 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
|
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 : RANDOMSHOW RANDOM DUP ;
Should I want to print out several without a loop construct I could save time by defining R : R RANDOMSHOW ;
|
FORTH
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. IF ELSE THEN 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 & IFSO
: 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. 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 diagramThe 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 result1234 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. |