www.jupiter-ace.co.uk

Previous Page > Index of General Forth Information > Going Forth - Part 4

Going Forth - part 4
Computing Today April 1982 page 91
D S PeckettGOING FORTH
The final part of our popular series sets out to explain the
operation and structure of a working FORTH program.

W
e have now looked at the main elements of FORTH and, after the initial shock, found it to be a very unusual language which has some significant advantages over 'conventional' languages such as BASIC. In particular, it runs about 10 times faster than your average BASIC and, once you have mastered the knack of thinking backwards, program development time can be considerably shortened. When you add to this the astonishing flexibility of FORTH and the fact that it is ideally suited to structured programming, i you start to wonder why you have been wasting your time with boring old BASIC, Pascal et al.
What we have not done so far though, is to put all these wild claims to the test by actually writing a FORTH program! This month we will, by means of the classic 'Towers of Hanoi' problem; there are a number of reasons for this choice:

a. It has well-established solutions which allow us to concentrate on writing a program without having to solve the fundamental problem as well.
b. It is a good example to show the sheer speed of FORTH.
c. It is the right size for an article like this.
d. Last, but not least, the Editor suggested it!
Remember that, where there might be any confusion, FORTH words and groups of words will be enclosed in square brackets - [ ]. The brackets themselves are not part of the language.

The Towers Of Hanoi
First of all, let me refresh your memory as to just what the 'Hanoi' problem is. There are lots of legends associated with it but in essence, the problem centres on three rods, one of which has a number of discs on it. The discs are of different sizes and are arranged so that any disc always has a smaller one on top of it. Your job is to move the file of discs to another rod, moving one at a time in such a way that a larger disc never lies on top of a smaller one.
Put like that it sounds simple, and it is. It just takes a terribly long lime — the minimum number of moves needed to transfer (n) discs is given by (2 n — 1). In other words, it would take 1023 moves
to shift a 10-disc pile, or 1,048,575 moves for 20 discs, Definitely a job for a computer.
There are many ways of solving the problem on a computer but the neatest, and perhaps the best known, uses a recursive algorithm. Recursion is a bogey word to some people but it really is nothing to be afraid of - all it means is that a subroutine can call itself. Usually each call nibbles away at the problem until, at the end of a whole series of nested calls, the problem is solved and the system backs its way out of the calls. For example, a recursive pseudo-language procedure to drink a glass of beer is:

Procedure DRINKBEER
Begin
Take a swig
If glass not empty then
DRINKBEER
End

Easy, isn't it - it makes you keep taking a swig until the beer's all gone and then you stop.
Suppose now that your 'Hanoi' set has three rods, numbered 0, 1 and 2. A recursive routine to move N discs from rod 'SOURCE' to rod 'DEST' is

Procedure HANOI(N,SOURCE,DEST)
Begin
IF (N>1) then HANOI(N-1,
SOURCE,(3-SOURCE-DEST))
Move disc N from SOURCE to DEST
If (N>1) then HANOI(n-1,
3-SOURCE-DEST),DEST)
End

The bracketed variables after the function name (HANOI) merely imply a mechanism for passing data into the routine.
I do not intend to go into the how and why of the procedure since that is not the object of this article; I simply ask you to accept that. it does work. If you want to know more about its action, try running through it with a pile of counters, a pencil, and some paper.

Specifying The
Program
What else must the program do? As well as implementing the algorithm, it must do a number of other things — in particular, it must give ways of starting, repeating and stopping the run.
Furthermore, it must also output the moves it is making. Since it is being written for a TRS-80 or Video Genie,  both  of which
have reasonable pixel graphics, the program should show the discs actually moving from rod to rod, and also print out which disc is being moved at any time. Finally, the program should be able to handle up to 20 discs and as there is no point in moving less than two, this implies a need for some sort of input checking.

Programming The
Solution
After the build up, take a look at Listing 1. You will see instantly just how odd a FORTH program can look. The listing fills six MMSFORTH blocks and I have numbered them 100-105. The operating system accesses blocks by number and 100+ is convenient.
Remember that FORTH programs, like Pascal ones, are constructed from a series of building blocks with the simpler words being compiled first so they can be used to . form more complex words. You should therefore start reading the program at the end of Block 105 where you see the word HANOI on its own. This is clearly being used in the immediate mode - it is not in a colon definition - and its job is to run the whole program automatically as soon as it has been compiled. In this way it is easy to give FORTH programs an auto-start capability.
HANOI is defined in line 12 of Block 105 and is formed from four major new words:- TITLE, INIT, SHIFT and AGAIN. The last three are nested in a BEGIN ....END loop to allow you to repeat the program as often as you like. INIT simply sets up the system, AGAIN checks to see if the program is to be run again, while SHIFT is the FORTH implementation of the algorithm above.
Before we go on to look at the four words of HANOI, study Block 100 which contains a number of utility words used throughout the program. The block starts with a TASK definition defining the start of HANOI in the system dictionary; this allows you to erase the whole program with a FORGET TASK.
Virtually all the program's calculations are performed on the stack but I found the need for a three element array holding the number of discs on each rod. Normal FORTH does not provide arrays so I had to extend the language to add them. The variable definition of PILETOTAL reserves two  bytes  in   the  system   for   it
Computing Today April 1982 page 92
PILETOTAL reserves two bytes in the system for it leaving a pointer, [H] to the next storage space for words or data. The [4H + !] simply increments [H] by 4, leaving PILETOTAL pointing to a reserved block of six bytes capable of holding the three elements of the array.
That is fine but we still need a way of implementing each element and, in particular, of getting any element onto the stack or of putting <MS> into any element. Suppose that we wish access element <n> by In PILETOTAL Remembering that executing the word PILETOTAL puts the address of the first of the six bytes in <TOS> , I hope that you can see that AGET, defined as [ SWAP 2* + ], converts that address and <n> into the address of the first byte of array element <n>. Think about it anyway. Having defined AGET - [A!] and [A@] are easy.
If you use this sort of construction, be careful. There is no array bound checking in AGET so there is nothing to prevent, say, [20 PILETOTAL A!]; this would undoubtedly crash the system by corrupting the dictionary. It was my choice not to check array bounds however and I could easily have extended AGET to do the job. (How?).
Block 100 also contains three other utility routines: 2DUP, 2OVER and [l>]. They are all very simple and 2OVER shows a typical application of <R and R>.
Line 12 of Block 100 gives the definition of TITLE, which displays the name of the program for a short period each time that it is run. It contains several FORTH words which may be new to you. CLS is an MMSFORTH extension for the TRS-80 and is identical to the CLS in Level II BASIC - it clears the screen and puts the cursor at top left. ECHO outputs the TOS value to the screen as an ASCII character; in this case, [23 ECHO] is the same as Level II's 'PRINT CHR$(23)' and selects double-width letters. PTC is another MMSFORTH extension and its job is to put the cursor at the row (0-15) defined by <20S> and the column (0-63) at <TOS>.
Wrapping-up Block 100; CHECKNO is used to adjust the value at TOS to lie in the range 2-20 inclusive. I described a similar word last month.
Let's go back to line 12 of Block 105. The next word used by HANOI is INIT, defined in line 2 of Block 103 from five other words. The first of these words,
GETNO, is straightforward and simply inputs and checks the number of discs to be moved. It also puts 2 and 0 at <30S> and <20S> respectively to define that discs will move from Rod 0 to Rod 2.
SETPILE'S only job is to set the three elements of PILETOTAL to the initial totals of discs on each rod. Rod 0 obviously receives the number at <TOS>, the number to be moved, while the other two are initialized to zero.
LINEDRAW uses the Level II graphics, accessing them directly via FILL, to draw a line across the bottom of the screen for the piles of discs to "stand" on. It also numbers the positions of the three rods by means of the PUT word defined in line 3 of Block 101. PUT uses [ <###> TYPE ] which operates on the value at <TOS> to give an effect equivalent to "PRINT USING "#"; N ;" in BASIC. The [ # ]  and  [ #> ]
define the start and end of the format field while the number of hash marks between them defines the width of the field to be output, Together they convert the number at <TOS> into a character string suitable for TYPE to output.
The next word in INIT is PILEDRAW which draws the number of discs at <TOS> on Rod 0 to define the start position. It is defined in line 11 of Block 102 and is basically a DO...LOOP setting up a number of calls to DISKDRAW which actually draws the discs. DISKDRAW expects to receive the number of the rod it is to draw on at <TOS>, the height (ie the number of disks on that rod) at <20S> and the disc number (which defines its size) at <30S>. SETUP then manipulates these values into suitable values for the graphics commands of DISKDRAW. The SETUP definition shows some typical FORTH arithmetic; it is quite difficult to follow and so Fig. 1. shows what happens on the stack when [10 12 1 SETUP] is executed.

Fig. 1. The stack before and after the execution of 10 12 1 SETUP.
Fig. 2. The screen display when the program is waiting for a user response.
Computing Today April 1982 page 93
GOING FORTH
DISKDRAW uses a MMSFORTH graphics extension, ESET. It works in a similar way to the Level II graphics commands; for instance, [y x ESET] is identical to BASIC's 'SET (x,y)'. Later on we will meet [ECLR], equivalent to L II's 'RESET ()'.

Shifting It
The most important new word in the program is, of course SHIFT, which implements the 'Hanoi' algorithm. The word is defined by lines 3-6 of Block 105; to follow it, you must recall that the 'N','SOURCE' and 'DEST' of the definition above are at <TOS> , <20S> and <30S> respectively whenever SHIFT is accessed. At least, the word assumes that the top three items of data on the stack represent that information.
With that data, it should be fairly easy to relate the sequence of SHIFT to the pseudo-language definition. Because all the data for the word is passed on the stack, the two words 1RECURSE and 2RECURSE are used to adjust the top three items to the values demanded by the algorithm. In fact, they both put three new items on top of the existing stack because each recursive call of SHIFT must preserve the existing parameters against the time that the program takes to work its way back down the nested list of calls. Figure 3 shows the action of 1RECURSE on a stack whose top three items are 8, 1 and 2. Since each call of SHIFT preserves the stack parameters, its final act must be to get rid of the top three items on the stack; if it did not do this, the stack would eventually overflow and crash the system.
SHIFT itself is not very complicated but one of its constituent words, MOVE, does quite a lot. This word actually shifts the discs around on screen and updates the program's counters. It does its work in the four stages implicit in the four words making it up.
The first job is to blank out the top disc on the 'SOURCE' (ie <20S> ) rod. BLANKDISK sets the height of the disc from the relevant element of PILETOTAL and converts the height (the number of discs in the pile) to screen-based coordinates.

Fig. 3. The stack building under the recursive use of 1RECURSE.
Using a DO...LOOP, it then blanks out a line of 44 pixels at that height, centred on the rod. Since the maximum disc width is 42 pixels ((disc No. 20) * 2 + 2), this guarantees to remove the disc from the display.
DRAWDISK then draws the same disc as the top element in the pile on the DEST ( <30S> ) rod. The word sets the numbers of the disc (and hence its size) and the destination rod (and hence the horizontal position) off the stack; the height of the new disc comes from a look at PILETOTAL(DEST). The disc is actually drawn by the DISKDRAW word which we met earlier; all the rest of DRAWDISK is concerned with setting up the stack to get the disc in the right place.
The third element of MOVE is ALPHA, which writes out the values of 'N', 'SOURCE' and 'DEST' in the right places in the progress line in the last line of the screen. The word pulls the relevant data off the stack, without disturbing the top three, or any other items.
The [DUP 10 < IF SPACE THEN] in ALPHA is used to line up the 'units' digit of the disc number in its field.
Finally, UPDATE adjusts the relevant elements of PILETOTAL to decrement the number of discs on the 'SOURCE' rod and increment the 'DEST' total. Its action should be clear from the code.
If you have kept up so far, Fig. 4 will come as no surprise. For the rest of you, read the description of the program again (a recursive read?) before you look at the photography illustrating the display on the screen part-way through a run of the program. As you see, it shows the discs and where they are as well as displaying which disc is being moved.
At the end of a run on the program, AGAIN is used to create a display like that of Fig. 5. The system is waiting for a yes/no response and, depending on the answer, the  BEGIN...END loop of HANOI will repeat the whole sequence or shut the system down.
Fig. 4. The screen display while discs are being transferred.
Computing Today April 1982 page 94
GOING FORTH
The Program In Use
That then, is a typical FORTH program. It is compact (most of the listing is blank space and/or comment and the compiled code occupies 1037 bytes) and it runs very, very fast. As an indication of its speed, it can transfer a 12-disc pile in 232 seconds. To put that in perspective, I wrote an equivalent BASIC program which was reasonably optimised to run quickly; it took 2220 seconds to move the same 12-disc pile. The program is so fast that it is quite impossible to see the individual discs moving. During its development I wished to see just what was going on and to do this, I needed to modify the second line of SHIFT to:

MOVE 1000 0 DO LOOP

to get it run slowly enough to follow.
In fact, most of the program's run is taken up with driving the graphics display which could be eliminated by altering MOVE to:

: MOVE ALPHA UPDATE ;

The 12-disc pile was then shifted in 100 seconds! A similar amendment to the BASIC version produced a run time of 530 seconds.

Conclusions
In this series, we have taken an introductory look at FORTH and the way that it should be used to write programs. This month's 'Towers of Hanoi' example gives a good idea of language might look like. It is not limited to gaming however, although its great speed makes it much more useful than BASIC for dynamic games. The language is becoming widely used for process control in such applications as machine-tools and astronomical equipment, where its speed, easy development and compactness make it very attractive.
In the future, we are likely to see a much wider use of FORTH as a personal computer language, bringing the advantages of structured programming and modular development to those who cannot afford the discs, etc needed to support the great god Pascal. There are already versions of the language available for virtually all common micros and most system owners can, in fact, choose from several implementations.
Those of you who have seen FORTH before will have realised that in this series, I have only skim- med the,  surface   of   it.   I   have   not 
	
		  
         0 ( BLOCK 100      1 OF 6    TOWERS OF HANOI          7/12/81     )
         1 (              A PROGRAM IN MMSFORTH                            )
         2 ( REQUIRES MMSFORTH GRAPHICS COMMANDS FOR TRS-80                )
         3 : TASK ;                       ( DEFINE THE START OF THE PROGRAM)
         4 0 VARIABLE PILETOTAL 4 H +!       ( PILETOTAL IS 3 ELEMENT ARRAY)
         5 : AGET SWAP 2 . ;             ( GET THE <20S> ELEMENT ONTO STACK)
         6 : A! AGET ! ;                            ( ARRAY EQUIVALENT OF !)
         7 : A@ AGET @ ;                            ( ARRAY EQUIVALENT OF @)
         8 : 2DUP OVER OVER ;          ( DUPLICATE <TOS> AND <20S> IN ORDER)
         9 : 2OVER <R OVER R> SWAP ;         ( PUT A COPY OF <30S> ON <TOS>)
        10 : 1> DUP 1 > ;                ( SAVE <TOS> AND TEST FOR BEING >1)
        11
        12 : TITLE CLS 23 ECHO 4 1 PTC          ( SELECT DOUBLE WIDTH CHARS)
        13              " WELCOME TO THE TOWERS OF HANOI"
        14              20000 0 DO LOOP ;                   ( A SHORT PAUSE)
        15 : CHECKNO 2 MAX 20 MIN ;             ( PUT <TOS> IN RANGE 2 - 20)
        
		
		
         0 ( BLOCK 101         2 OF 6 TOWERS OF HANOI          7/12/81     ) 
         1
         2 ( DRAW THE BASE LINE ON WHICH DISCS WILL HE MOVED               )
         3 : PUT 133 ECHO <# # #> TYPE 138 ECHO ;       ( DRAW ROD NLIABERS)
         4 : LINEDRAW CLS 143 16256 64 FILL 14 9 PTC 0 PUT
         5                 14 30 PTC 1 PUT 14 51 PTC 2 PUT ;
         6
         7 ( INPUT AND CHECK THE NUMBER OF DISCS WHICH ARE TO BE MOVED     )
         8 : GETNO CLS 2 0 6 5 PTC                   ( 2, 0 DEFINE TO, FROM)
         9         " HOW ANY DISCS DO YOU WANT TO MOVE (2-20)"
        10         #IN CHECKNO ;                ( EXIT WITH NUMBER ON <TOS>)
        11
        12 ( INITIALISE ROD TOTALS - ALL DISCS ON ROD 0, OTHERS EMPTY      )
        13 : SETPILE DUP   0 PILETOTAL A! 0 1 PILETOTAL A!
        14               0 2 PILETOTAL A! ;
        15 : LINECLEAR 32 16320 64 FILL ;               ( CLEAR BOTTOM LINE)
       
	   
	    
         0 ( BLOCK 103         3 OF 6 TOWERS OF HANOI          7/12/81     )
         1
         2 ( WHEN TOS=A, 2OS=B ,3OS=C, DRAW DISC 'C' HEIGHT 'B' ON ROD 'A' )
         3 ( SET UP THE STACK FOR DISKDRAW:                                )
         4 ( TOS=XSTART OF DISC, 2OS-XFINISH OF DISC, 30S=YPOSITION        )
         5 : SETUP SWAP 42 SWAP 2* - ROT ROT             ( YPOSITION=42-2*B)
         6              42 * 20 + OVER - DUP <R          ( XSTART=42*A+20-C)
         7              SWAP 2* 2 + + 8> ;           ( XFINISH=XSTART+2*C+2)
         8 : DISKDRAW SETUP DO DUP I ESET LOOP DROP ;       ( DRAW THE DISC)
         9
        10 ( DRAW THE TOTAL NUMBER OF RODS TO BE MOVED ON ROD 0 POSITION   )
        11 : PILEDRAW DUP 0 DO DUP I - I 1+ 0 DISKDRAW LOOP ;              )
        12 ( WAIT UNTIL READY TO START, AND SET UP BOTTOM LINE             )
        13 : WAIT BEGIN LINECLEAR 15 26 PTC " READY" Y/N NOT END
        14              LINECLEAR 15 14 PTC
        15              " MOVE DISC FROM ROD TO ROD " ;
       
	   
	   
         0 ( BLOCK 104      4 OF 6    TOWERS OF HANOI          7/12/81     )
         1
         2 : INIT GETNO SETPILE LINEDRAW PILEDRAW WAIT ;       ( INITIALISE)
         3 : ADEC AGET -1 SWAP +! ;            ( DECREMENT AN ARRAY ELEMENT)
         4 : AINC AGET 1 SWAP +! ;             ( INCREMENT AN ARRAY ELEMENT)
         5 : UPFROM OVER PILETOTAL ADEC          ( DECREMENT THE 'FROM' ROD)
         6 : UPTO 2OVER PILETOTAL AINC ;           ( INCREMENT THE 'TO' ROD)
         7 : UPDATE UPFROM UPTO ;        ( UPDATE RECORD OF QTY ON EACH ROD)
         8 ( PRINT WHICH DISC IS MOVED, AND THE MOVE THAT IT TAKES         )
         9 : ALPHA 15 23 PTC DUP DUP 10 < IF SPACE THEN .            ( DISC)
        10         15 35 PTC OVER . 15 44 PTC 2OVER . ;              ( RODS)
        11
        12 ( DRAW THE MOVED DISC IS ITS NEW POSITION                       )
        13 : DRAWDISK 2OVER SWAP SWAP ROT DUP PILETOTAL A@
        14            I+ SWAP DISKDRAW ;
        15

         0 ( BLOCK 105      5 OF 6    TOWERS OF HANOI          7/12/81     )
         1
         2 ( BLANK THE DISC THAT IS TO BE MOVED FROM ITS OLD ROD           )
         3 : BLANKDISK OVER DUP PILETOTAL A@ 2* 42 SWAP -       ( YPOSITION)
         4            SWAP 42 * DUP 44 + SWAP          ( XSTART AND XFINISH)
         5            DO DUP I ECLR LOOP DROP ;              ( BLANK IF OUT)
         6
         7 ( MOVE THE TOS DISC FROM 2OS ROD TO 3OS ROD                     )
         8 : MOVE BLANKDISK DRAWDISK ALPHA UPDATE ;
         9
        10 ( ADJUST STACK FOR RECURSIVE CALLS OF SHIFT          (SEE TEXT) )
        11 ( BOTH THE WORDS PRESERVE THE DATA ALREADY ON THE STACK         )
        12 : 1RECURSE 2OVER 3 SWAP - 2OVER - 2OVER 2OVER 1 - ;
        13 : 2RECURSE 2OVER 2OVER SWAP DUP ROT +3 SWAP - 2OVER 1 - ;
        14
        15
        
          
         0 ( BLOCK 106      6 OF 6    TOWERS OF HANOI          7/12/81     )
         1
         2 ( SHIFT IS THE WORD THAT ACTUALLY CALCULATES THE HANOI SEQUENCE )
         3 : SHIFT 1> IF 1RECURSE SHIFT THEN               ( RECURSIVE CALL)
         4 : MOVE                            ( ACTUALLY MOVE THE RIGHT DISC)
         5         1> IF 2RECURSE SHIFT THEN               ( RECURSIVE CALL)
         6         DROP DROP DROP ;                     ( TIDY UP THE STACK)
         7
         8 ( OFFER THE CHANCE FOR ANOTHER RUN, AND ACCEPT THE ANSWER       )
         9 : AGAIN LINECLEAR 15 26 PTC " AGAIN" Y/N ;
        10
        11 ( FINALLY, HANOI IS THE WORD THAT FORMS THE WHOLE PROGRAM       )
        12 : HANOI TITLE BEGIN INIT SHIFT AGAIN END ;
        13
        14                              HANOI                     ( RUN IT!)
        15
Listing 1. The complete MMSFORTH listing of the solution
to 'The Towers Of Hanoi' problem. The 'screen' format has
been retained.
Computing Today April 1982 page 95
GOING FORTH
even looked at how strings and double-precision and/or floating-point numbers could be provided; neither have I given any indication of how to provide the essential feature for all gamesters, a random-number generator. Most commercial FORTHs include such features but, when they do not, it is always easy to add them.
The language is not just limited to defining new words from old, powerful though that feature is. With only a little more effort, we can create whole new classes of words by defining new defining words. With such a facility we could, for instance, have created a new word type called ARRAY allowing us to access any element of an n-dimensional array without the fiddling about we had to use in HANOI. FORTH is truly limited only by your own imagination. I hope that some of you will want to sample it further and join the ranks of those who GO FORTH.
Fig. 5. All done! The program will let you repeat the sequence using a different
number of discs if you wish.