Forth part XIII

Why did I come so far ? 
Guess I must have forgotten 
that I'd have to walk back again too !  
Hilah Paulmier and Robert Haven Schauffler - Peace Days


                      
                           STRENGTH IN FORTH

                             part thirteen

                 SOME LESSONS IN LATIN AND OTHER STUFF

There happens to be something evil in the air regarding this part 
of  the FORTH-course and it may bring me a lot of  misfortune.  I 
can smell it !!  Part thirteen !!  And I already saw a black  cat 
this  morning  too !  Long ago (?) superstition was  very  common 
among us,  people. Animals are far too smart to be superstitious. 
Yes,  a dog will get mad at the sight of a black cat and at a red 
one too,  to prove that it's its nature.  Perhaps it is mankind's 
nature to be superstitious. Who knows ? It seems they love to get 
frightened  in  some  irrational way mostly  by  pretty  harmless 
animals or events.

RUNNING AROUND

In the same way,  some people are afraid of words:  especially of 
so called difficult words,  even if you tell one,  that there are 
no  difficult words.  People themselves are often more  difficult 
than the words they speek.  If we speek about computers and about 
all  that can be done with them,  we often encounter  'difficult' 
notions.  Let me name one: recursion. It's Latin and I can assure 
you  that it was not a difficult word to those Romans  conquering 
the  world as they thought they did 20 centuries  ago.  Recursion 
consist of two parts:  re and cursion,  in Latin:  re and curere. 
The first word isn't really a word.  It is a prefix.  It is often 
put  in front of a verb or a noun to indicate,  that  some  event 
happens  again  and  again.  The word curere  means  to  run.  So 
recursion may be translated by  to rerun. In computerenvironments 
it  has  something to do with a program or a part of  a  program, 
that has in effect to be rerun in one way or  another.  Yes,  and 
curere  has  much to do with cursor (a runner) and  a  course:  a 
learning-program that you 'run' through.  And with a carreer.  If 
you were an Arab, you wouldn't have written the vowels of a word. 
It's  common use in Arabian languages to left out  those  sounds. 
Now if you act with the 'curere'-words as an Arab,  you will find 
out  that  crr and crs are the favourite  letter-combinations  of 
this Latin word. They appear in curere and carreer, in cursor and 
course.  And in French courir (crr) means to run. You see, it all 
sticks together. So, recursion is related to 'repeat' ? In a way, 
yes ! In another way, no ! If recursion would have been identical 
to repetition,  then the repeated action inside a loop could have 
been called recursion too !  The one  restriction with a loop is, 
that  a  loop does NOT repeat ITSELF in itself  as  a  loop.  The 
other  is,  that you can't start the loop again from  within  the 
loop.  And  the BEGIN..WHILE...REPEAT-loop,  what about  it,  you 
might  have argued,  if you had carefully thought over  my  above 
statements (Which you did NOT,  did you ?). That objection is not 
a  valuable  one.   Because  you  can't  jump  nor  from   within 
BEGIN..WHILE nor from within WHILE..REPEAT to BEGIN.  If what has 
been said above,  is all clear to you,  we can add  the following 
statement: a recursive action is an action which uses itself as a 
part  of its own definition.  In FORTH a recursive definition  is 
often and easily recognised by the word {MYSELF}. So

: RERUN  (words)   MYSELF  (more words)  ;

is  a recursive definition.  The execution of {RERUN} will  at  a 
certain  moment  execute {MYSELF},  which causes a call  back  to 
{RERUN}. The word {MYSELF} is a most popular solution in FORTH to 
the problem of how to construct recursive  definitions.  {MYSELF} 
will  find  the address of the namefield of  the  word  currently 
being defined first, then it will calculate the compilation field 
address and compile this address into into the  dictionary.  It's 
an immediate word,  because it has to execute during  compilation 
of the word in which it is used. The following example is a quite 
complicated one regarding the fact,  that this course happens  to 
be for beginners only.  Don't type it at your terminal. Executing 
this  example may cause a returnstack overflow or your FORTH  may 
start  doing  crazy things.

:  ?THOUSAND  ( n --- n.....1000  )          
          DUP 1000 <
              IF 1+
                 CR DUP .
                 MYSELF
              THEN
;  

A ROUTINE OF A SORT

Nevertheless this definition is recursive all the way.  What will 
this definition do, if we execute it in our minds. As you can see 
by the stacknotation, a number is expected. Try this one

1230 {?THOUSAND} OK

Your  computer  wouldn't have collapsed if you had  entered  that 
line.  The {IF..THEN}-structure would have jumped directly beyond 
{THEN},  as the result of the comparison 1230 1000 {<} is  false. 
So  the sequence inside the {IF..THEN} isn't executed.  I  simply 
avoided the confrontation with {MYSELF} ! Try next one

950 {?THOUSAND} 950 951 etc....1000 OK

The output at your screen is vertically instead,  but still there 
will  not  be a hang-up of your machine.  I  tested  4  different 
FORTH-systems:  two of them - after 57 and 67 calls from {MYSELF} 
to {?THOUSAND} respectively - displayed OK and that was  it.  One 
system  could  stand 510 calls and then  warned  me:  Returnstack 
overflow.  The  last  one  also held it for 510  calls  and  then 
collapsed without any message or proper warning. So recursion has 
its limits, set by the size of the returnstack. Last try......

400 {?THOUSAND} 401 .........??????????????

From the above follows,  that this sequence will not do,  what it 
was intended to do when I defined the definition of  {?THOUSAND}. 
That definition says:  if a number is smaller than 1000, add 1 to 
that  number,  take a new line,  duplicate the increased  number, 
take the duplicate one from the stack and print it at the  screen 
and  then  branch to {?THOUSAND} again to test if the  number  is 
still  smaller  than 1000,  if so add 1 again  etcetera.  If  the 
number  is  not  smaller than 1000  any  longer,  then  the  word 
{?THOUSAND} will end.  Of course the phenomenon of a  returnstack 
being  too  small  to hold a thousand  numbers  is  worth  asking 
questions  about  it.  This returnstack has never caused  us  any 
trouble so far. But before I'll try to answer that question, I'll 
try  to comfort you.  I'll give you a recursive word which  is  a 
quicksort-routine.  In part 8 of this course I gave you a bubble-
sorting routine. Some of the code involved in that routine we are 
going to use here too.

: LARRAY  CREATE 4* ALLOT 
          DOES>  SWAP 4* + 
;

256 LARRAY S-D
511 CONSTANT RAND

: FILL-ARRAY  256 0 DO 
                      RAND RND I S-D !
                    LOOP
;

: SHOW-ARRAY 252 12 / 0 DO 
                          12 0 DO
                                 J 12 * I + S-D @
                                 6 .R 
                               LOOP CR
                        LOOP
;

: I'  RP@ 4 + @ ;

: I'' RP@ 8 + @ ; 
  
: QSORT 2DUP >R >R I' I'' + 2/ S-D @
            BEGIN 
                BEGIN I' S-D @ OVER < WHILE R> 1+ >R       REPEAT
                BEGIN DUP I'' S-D @ < WHILE R> R> 1- >R >R REPEAT
                I' I'' > NOT IF
                     I' S-D @ I'' S-D @
                     I' S-D ! I'' S-D !
                     R> 1+ R> 1- >R >R 
                             THEN
    I' I'' > UNTIL
          DROP R> SWAP ROT R>
          2DUP  < IF       MYSELF THEN
          2OVER < IF 2SWAP MYSELF THEN
          2DROP
;

: QUICKSORT  QSORT 2DROP ;

FROM HIGH TO LOW AND BACK
 
First  I'll  better tell you how to use it,  then  I'll  give  an 
explanation of how it works and last of all I'll show you how  to 
adapt it - if necessary - to your system. The {QUICKSORT}-word in 
this form will sort from low to high 256 randomely chosen numbers 
in less than a second. The numbers are put into an array {S-D} by 
the  word {FILL-ARRAY}.  If you want to have a look at the  newly 
filled  array,  then type {SHOW-ARRAY} and on a  b/w-monitor  252 
numbers  will be displayed neatly grouped into columns.  Now  you 
can  sort the numbers by typing 0 256 {QUICKSORT}.  After the  OK 
has  been displayed almost immediately,  type {SHOW-ARRAY}  again 
and  you will see that the numbers are sorted from low  to  high. 
Now  for the algorithm itself.  The word {LARRAY} is an  defining 
word.  It allows to define arrays which can hold 32 bit  numbers. 
{S-D} is such an array, capable of holding 256 items. With {FILL-
ARRAY} we can fill {S-D} with 256 random numbers.  This word uses 
the  word {RND},  which stands for a  random-numbergenerator.  In 
this case that generator expects two numbers - {RAND} (= 511) and 
{I}. The latter indexes into the array. In {SHOW-ARRAY} I lowered 
the number of array-elements to 252,  because that can be divided 
by 12 easily without any modula,  to get a nice looking output at 
the  screen.  The  following  two words bring us  closer  to  the 
target.  As you will remember from part 12, the returnstack grows 
downward into memory. The returnstackpointer always points to the 
next  free  stackspace,  so by adding 4 to that pointer  it  will 
point to the last item that was put there and by adding 8 it will 
point to the previous element.  Notice that 4 and 8 indicate that 
this code was ment for a 32 bit FORTH.  The words {I'} and  {I''} 
have been defined to have the opportunity to COPY the two topmost 
elements  from the returnstack to the parameterstack.  The  words 
{>R}  and (R>} REMOVE the topelement from the  parameterstack  to 
place  it on top of the returnstack and  vice-versa.  Let's  dive 
into  the  deep  world of {QUICKSORT}  and  examine  the  phrase: 
2DUP >R >R I' I'' + 2/ S-D @.  The  word {QUICKSORT} expects  two 
numbers.  The smaller number indicates the start- and the  higher 
the  end-element of the array {S-D} you want to be sorted.  3  10 
{QUICKSORT} for instance will sort the elements 3 4 5 6 7 8 9 10. 
To have the whole array sorted,  use 0 256 as the parameters  for 
{QUICKSORT}.  These  two  numbers are dupped.  Then one  pair  is 
removed to the returnstack. From there this pair is copied to the 
parameterstack again, added together and divided by two.

THE ESSENCE OF A PIVOT

The stack now holds three numbers 0 256 128.  Notice that in this 
way  we always get a number on top of the stack that  is  halfway 
the  two numbers we put there in the beginning.  That means  that 
128 {S-D} {@} will fetch the number that is stored in the  middle 
element  of  the  array.   This number is often  referred  to  as 
'pivot-value'.     Remember  that  this  is  essential  for   the 
quicksort-routine  in what language whatsoever.  As you can  see, 
the  routine  shows three loops starting with the  word  {BEGIN}. 
There  is  one big  {BEGIN...UNTIL}-structure,  inside  of  which 
reside two {BEGIN...WHILE...REPEAT}-clauses.  The first of  these 
clauses copies the top of the returnstack (here the number 0)  to 
the  parameterstack  to serve as an index into the  array  {S-D}. 
Then  the  contents  of the number zero element  is  fetched  and 
compared with the 128th element.  If this number zero element  is 
smaller than the 128th one, we remove the 0 from the returnstack, 
add one to it and place it back.  With {OVER} we kept 128 on  the 
parameterstack  for further use as will follow.  Then  we  branch 
back to {BEGIN},  again we copy the top of the returnstack to the 
parameterstack - the top being 1 now !!!!!! -, fetch the contents 
of  the number one element and compare it with the 128th  element 
etc.  As  long  as the value in the element we  indexed  into  is 
smaller than the pivot-value, that value is allowed to stay where 
it is. If not, we will enter the second {BEGIN...WHILE...REPEAT}-
structure.  In this structure we act almost in the same way as in 
the loop we just left,  except we will now compare the  rightmost 
element (number 256) of  the array - found with {I''} - with  the 
128th  one,  the pivot-value.  If this pivot is smaller - so  the 
value  in  the element  at the right side of  the  128th  element 
being  higher  - the rightmost element stays  where  it  is,  the 
second   number   on   the  returnstack   is   removed   to   the 
parameterstack,  1  is  subtracted and 255 is replaced  onto  the 
returnstack.   And as long as the value stored in the 255th,  the 
254th,  the  253rd  and etcetera element of the  array  {S-D}  is 
higher  than  the pivot,  nothing happens and the  loop  repeats. 
But....if  that last statement is not true AND the topelement  on 
the   returnstack  is  not  higher  than  the   second   element, 
(I' I'' > NOT IF),  then we will exchange values.  Remember, that 
we left the first {BEGIN...WHILE...REPEAT}-loop,  when the  value 
in  the {I'}th element appeared to be higher than the  pivot  and 
that  we  left  the second loop,  when the  {I''}th  element  was 
smaller. Notice, that the pivot-value is not likely to be exactly 
the middlest value in the range of 0 - 511. It could be any value 
in that range, because we stored 256 RANDOMLY chosen numbers into 
the  successive elements of the array.  After the  exchange  took 
place,   we  increment  {I'}  and  decrement  {I''}.   This   two 
comparisons and the exchange of values are repeated until the two 
indexpointers  cross - {I'} {I''} {>} {UNTIL} i.e.  the value  of 
{I'} grew just one more than the value of {I''}.  Then we have to 
leave the big {BEGIN}-loop.  We drop the pivot value and put  the 
value  of {I'} onto the parameterstack.  On that stack we left  0 
256 still from the beginning.  So the stack shows 0 256 and {I'}. 
With {ROT} we put the 0 on top:  256 {I'} 0.  Then we remove  the 
value of {I''} from the returnstack onto the parameterstack.  Now 
we have gathered there 4 numbers:  256 {I'} 0 {I''}.  In this way 
we've  got  as far as {MYSELF} and the game will start  all  over 
again.  But...watch the difference:  we use only one new starting 
value,  as  we  used 0 as a starting value also the  first  time.

TO STAY OR NOT TO STAY INSIDE !
 
Let's assume,  {I''} had the value of 139, though it might be any 
value.  The stack will hold 256 {I'} 0 139.  Be aware of the fact 
that  between the zero and the 139th element of the  array  {S-D} 
only  numbers  smaller  than  the  pivot-value  are  stored  now.
To sort this row with {MYSELF} i.e.  {QSORT} we have to choose  a 
new second pivot-value.  Again all elements between zero and  139 
are  sorted in two rows:  a left row containing values less  than 
the  pivot-value,  a right row with all the higher  values.  This 
process  continues  till  all  left and  right  rows  are  sorted 
completely.   It is obvious,  that if the pivot-values happen  to 
be low numbers again and again,  the sorting-time will increment. 
But it is not likely,  that the pivot-value will be a low  number 
each  time  it is chosen.  The last word in {QSORT}  is  {2DROP}. 
Because  {QSORT}  is a recursive routine it should  left  on  the 
parameterstack as many parameters as there were in the beginning. 
The  word {QUICKSORT} will remove this two parameters  after  the 
sorting  has  been completed.  It is striking to  see  that  this 
{QUICKSORT} needs much less than 67 calls to {QSORT} to sort  the 
array. So even a small returnstack can hold all returnaddresses.
It  should be worthwhile to investigate the maximum-length of the 
array  which  can  be sorted at a  given  maximum-length  of  the 
returnstack;  in other words, when  will the returnstack  set the 
limit.  So  we are back with the question,  WHY the size  of  the 
returnstack  determines  the  depth of a  recursive  routine  and 
meanwhile the length of an array to be sorted ?  Take a good look 
at the definition of {QSORT}.  This word is the recursive part of 
{QUICKSORT}.  The  call to {QSORT} with the word {MYSELF}  always 
occurs from inside {QSORT}.  We never leave {QSORT} at {;} to run 
it  again.  The  inner  live of FORTH now forbids  to  clear  the 
returnstack  from within a word.   Each call to {QSORT} causes  a 
new returnaddress to be placed on the returnstack.  Normally  the 
size  of  the returnstack will be large enough to  hold  all  the 
returnaddresses.  But  with  a  recursive definition  it  is  not 
always  possible  to  foresee the amount of calls  that  it  will 
make. 

KNOWING YOURSELF

To  understand  the  action  of  {MYSELF},   let's  look  at  its 
definition.
 
: MYSELF  ?COMP LAST @ NAME> , ; IMMEDIATE

This  definition may vary among different systems.  Sometimes  it 
isn't  even there and you will have to define  it  yourself.  The 
exact  syntax  of that definition depends on the system  and  the 
words it provides.  But the explanation of {MYSELF} will give you 
as  much information as you need to be able to define a  sort  of 
{MYSELF}  in  each FORTH you know about.  First of  all  {MYSELF} 
checks  if FORTH is in a compiling mood.  If not the system  will 
abort  and a message will be displayed.  The word {?COMP} may  be 
left  out  as  well,  as  it only serves  to  be  sure  FORTH  is 
compiling. Then {LAST} is executed. This word leaves on the stack 
the   address  of  the  uservariable  in  which  is  stored   the  
namefield-address of the last entry in the dictionary. This is of 
course  always  the namefield of the word in  which  {MYSELF}  is 
used.  So in {QSORT} this uservariable holds the namefieldaddress 
of {QSORT}.  With {@} we get this namefieldaddress out of  {LAST} 
and  put  it  on the stack.  The {NAME>} comes  into  action  and 
converts    the    namefieldaddress    into    the     consequent 
codefieldaddress,  which is compiled into the dictionary by  {,}. 
So {MYSELF} puts the codefieldaddress of the word it is used  in, 
into  the parameterfield of that word,  as if it were one of  the 
many other words that have to be carried out by that last word.
It  is  not said here,  that the method of recursion  which  uses 
{MYSELF} is the only possible method to program recursive  words. 
As  we  shall see when we discuss  executionvectors  and  forward 
references, recursive techniques are also made possible by them.

BEING SILLY

Two  more  'difficult' words fell:  executionvector  and  forward 
reference.  Let's  start  with  the  explanation  of  the  notion 
'executionvector'. So enter this silly word

: FIRSTWORD    ." This is firstword " : OK

Now we are going to use {FIRSTWORD} with the following word

: FOLLOWING   FIRSTWORD   ." used in following." ; OK

Executing {FIRSTWORD} gives

{FIRSTWORD} This is firstword OK

And executing {FOLLOWING} is even more boring

{FOLLOWING} This is firstword used in following OK

As you will remember, it is allowed to redefine a word. So

:  FIRSTWORD    ." This is redefined firstword" FIRSTWORD is  not 
Unique OK

will work correctly. 

{FIRSTWORD}  This is redefined firstword OK

But what about {FOLLOWING} ? Which of the two {FIRSTWORD} will it 
use now ? Let's give it a try

{FOLLOWING} This is firstword used in following OK

It's   quite   clear:   {FOLLOWING}  stuck  with   the   original 
{FIRSTWORD}. It did not switch to the redefined {FIRSTWORD}. 

: FOLLOW-UP  FIRSTWORD ." used in follow-up " ;

As you are going to see now

{FOLLOW-UP}  This is redefined firstword used in follow-up OK

{FOLLOW-UP} used the redefined version of  {FIRSTWORD}.  Remember 
the  next rule.  Each word that uses another word to  define  its 
action,  will  use  the  current version of that  other  word  to 
compile into its dictionary-entry.   When executed,  it will also 
use  the version of that other word that was current at  compile-
time.  If after a word has been defined using another word,  that 
other  word  is  redefined,  then the action  of  that  redefined 
version will only appear in words defined AFTER the  redefinition 
of  that other word.  So if a word has been redefined,  then  the 
original word can't be used any more in new words. Suppose, it is 
your  deepest and most secret desire to use the  old  {FIRSTWORD} 
into a new word. All money in the whole world would not be enough 
to  make that dream comes true.  But for less than that  I   will 
tell you a secret way-out of terifying dilemma.  The simple spell 
is  called 'executionvector'.  And of course FORTH  provides  all 
means  to  construct  this phenomenon.  You  could  see  upon  an 
executionvector  as  an  army sees  upon  its  base.  From  there 
military  actions of all kind are carried out in all  directions, 
but  each  separate action starts at the base.  An  example  will 
clarify things a little. Please enter

: FIRSTTRY   ." This is an example." ; OK

: SECONDTRY  ." This is another one." ; OK

I SEE..

We now will define a third word,  called {YOUSEE}. This word will 
have  to execute {FIRSTTRY}.  We will not define this word  as  a 
direct colon-definition, such as

: YOUSEE  FIRSTTRY ;

but we will make the execution work in a more roundabout way.  To 
execute a word,  we have to put its cfa on the stack and then use 
{EXECUTE}.  It  doesn't matter how the cfa was put on the  stack. 
So, if the cfa was first stored into a variable, we could {@} the 
contents of that variable and then use {EXECUTE}. Let's try it

{VARIABLE} VECTOR OK

{'} {FIRSTTRY} {NAME>} {VECTOR} {!} OK 

The  sequence {'} {FIRSTTRY} finds the pfa  of  {FIRSTTRY}.  Then 
{NAME>}  converts  the pfa to the cfa and with {!}  this  cfa  is 
stored into {VECTOR}. We now will define {YOUSEE} as

: YOUSEE VECTOR @ EXECUTE ; OK

Executing  {YOUSEE} will write the action of {FIRSTTRY}  at  your 
screen

{YOUSEE} This is an example OK

as  could  be expected.  The point of working  in  such  indirect 
manner  is  that  we  can simply change  what  {YOUSEE}  does  by 
changing the contents of the variable {VECTOR}. Just enter

{'} {SECONDTRY} {NAME>} {VECTOR} {!} OK

Now the contents of {VECTOR} is the cfa of {SECONDTRY}. So

{YOUSEE} This is another one OK

will  be  the action of {YOUSEE}.  We didn't have to  change  the 
definition  of  any word we previously defined,  we only  had  to 
change the contents of a variable.  With this method you can have 
{YOUSEE} execute literally every word in the dictionary,  without 
changing  anything but the contents of {VECTOR}.  We have  proved 
that  it is possible to change the action of a word - {YOUSEE}  - 
AFTER it has been defined,  without redefining it.  This leads to 
the  conclusion,  that all compiled references to  {YOUSEE}  will 
also  change their action.  That's because {YOUSEE} will  execute 
whatever  word  whose executionaddress is held  by  the  variable 
{VECTOR}.  This variable {VECTOR} is known as the executionvector 
for {YOUSEE}. This facility is very useful, but some problems may 
arise  with  the  use of the simple method  we  described  above. 
Suppose you forget to store a reasonable address in the variable. 
This  could  cause some spectacular crashes !!  There  isn't  any 
check made in this direction. Furthermore - although an Atari has 
quite  a lot of memory - this method is very inefficient  in  the 
use of memory.  And we like to be efficient,  don't we ?  So most 
FORTHs   have   some   alternative   method   of   defining    an 
executionvector.  The  main difference between one FORTH and  the 
other  in this case is the name of the defining word  which  will 
create a vectored word. The method is always the same. Therefore

{FORGET} {YOUSEE} OK

{DEFER} {YOUSEE} OK

Now {YOUSEE} has become a vectored word. As long as no action has 
been  assigned to {YOUSEE},  a default vector to a  routine  that 
will  give  an  error-message  becomes  active  on  execution  of 
{YOUSEE}.

{YOUSEE} 
YOUSEE <--- DEFERRED WORD NOT INITIALISED OK

The assignment of an action to {YOUSEE} is quite simple.

{'} FIRSTTRY {IS} {YOUSEE} OK

In this way {YOUSEE} will carry out the action of {FIRSTTRY}.  As 
with the variable {VECTOR},  it is possible to change the  action 
of {YOUSEE} by the assignment of another word. Define

: THIRDTRY ." And this is a third action !!" ; OK

{'} {THIRDTRY} {IS} {YOUSEE} OK

Executing {YOUSEE} will execute {THIRDTRY},  but there is a  main 
difference  between  {YOUSEE} executing {FIRSTTRY}  and  {YOUSEE} 
executing {THIRDTRY}.  In executing {THIRDTRY} {YOUSEE} has  been 
used  as a forward reference.  In respect to {FIRSTTRY}  {YOUSEE} 
carries  out a previously defined action and that's quite  normal 
in FORTH. In the case of {THIRDTRY} {YOUSEE} was defined to carry 
out  a  word  that still has to  be  defined:  {YOUSEE}  referred 
forwardly to a word still to come.  The normal compiling  process 
can  only compile the address of a word that has previously  been 
defined and thus can be found in the dictionary.  As we saw above 
the  use of execution vectors provides a simple solution  to  the 
problem of including a reference to a word that has not yet  been 
written.  A still simpler solution is to define the words in  the 
correct sequence.  But the use of forward references can become a 
extremely  elegant  programming technique in the form  of  mutual 
recursion:  two words calling each other.  In this case it cannot 
be  avoided to use a forward reference.

DRAWING A COSY CORNER...
  
The next example  shows what is ment here

NEEDS DRAW     LINEA.FTH                                      (1)  

GRAPHICS                                                      (2)

FORTH DEFINITIONS  DECIMAL                                    (3)

6 CONSTANT N    384 CONSTANT H0                               (4)
 
VARIABLE X1     VARIABLE Y1  VARIABLE H                       (5)
VARIABLE X0     VARIABLE Y0  
VARIABLE X      VARIABLE Y

: XYPLOT Y1 ! X1 ! ; ( X-coor Y-coor --- )                    (6) 

: PLOT 2DUP X1 @ Y1 @ DRAW XYPLOT ; ( X-coor Y-coor --- )     (7)

: XYLINE X @ Y @ PLOT ;

: X+  H @ X +!  XYLINE ;           : Y+ H @ Y +!  XYLINE ;    (8) 
: X-  H @ NEGATE X +! XYLINE ;     : Y- H @ NEGATE Y +! XYLINE ;

DEFER DRAW-SIDES                                              (9) 

: 3SIDES OVER DUP IF 1- SWAP DRAW-SIDES 
                  ELSE 2DROP
                  THEN ;

: OR1 3 3SIDES X-  0 3SIDES Y-  0 3SIDES X+  1 3SIDES DROP ; (10)
: OR2 2 3SIDES Y+  1 3SIDES X+  1 3SIDES Y-  0 3SIDES DROP ;
: OR3 1 3SIDES X+  2 3SIDES Y+  2 3SIDES X-  3 3SIDES DROP ;
: OR4 0 3SIDES Y-  3 3SIDES X-  3 3SIDES Y+  2 3SIDES DROP ;

4 CASE: (SIDES) OR1 OR2 OR3 OR4 ;                            (11)

' (SIDES) IS DRAW-SIDES                                      (12) 

: INITIALISE  H0 DUP H ! 2/ DUP X0 ! Y0 !  ;                 (13) 

: XYSET  H @ 2/ DUP H ! 2/ DUP X0 +! Y0 +! X0 @ Y0 @         (14)  
         2DUP  Y ! X ! XYPLOT ;

: PLOT-IT ERASE-SCREEN INITIALISE                            (15) 
          0 BEGIN 
                  1+ XYSET 0 3SIDES DUP N = 
            UNTIL 
                 DROP KEY DROP ERASE-SCREEN ;

This little drawing-routine is a adaptation for the Atari ST from 
a  FORTH-program on the BBC-computer.   The first line checks  if 
the word {DRAW} has been defined.  If not the file LINEA.FTH will 
be loaded and compiled.  This file contains a FORTH-interface  to 
the LineA-drawing-routines. {GRAPHICS} initialises these drawing- 
routines.  Line (3) will place the following words in the  FORTH-
vocabulary.   Line  (4)  and  (5)  defines  some  constants   and 
variables.  {XYPLOT}  at line (6) is a help-word for  (PLOT);  it 
remembers  the end-coordinates of a line,  so the following  line 
will start at that point. The four words marked (8) will increase 
(X+  ,  Y+) or decrease (X- ,  Y-) the screen-coordinates and   a 
line  is drawn from the old to the in- or decreased  coordinates. 
The lines (9),  (10) and (11) form the heart of this program.  At 
(9) the execution-vector {DRAW-SIDES} is created;  as you can see 
at (12) it will be assigned to execute {(SIDES)}.  In the  'main' 
word  {PLOT-IT}  the  execution  of  {3SIDES}  sets  the   mutual 
recursive  action  at work.  The word {3SIDES} - at (10)  -  will 
call  {DRAW-SIDES},  which  will execute  {(SIDES)},  which  will 
execute  one of the four {ORx} words,  which will call  {3SIDES}, 
which will call {DRAW-SIDES}, which will call via {(SIDES} one of 
the four {ORx} words, which.......etc. You may try of course, but 
it will soon become clear, that it is impossible not to define an 
execution-vector and yet run this program.  This program contains 
also a positional case word {CASE:}.  It is a defining word. Here 
it defines {(SIDES)} to have four cases:  4 {CASE:} {(SIDES)}. It 
depends  on  the value - 1,  2,3 or 4 - which of the  four  words 
following {(SIDES)} will be executed. So 2 {(SIDES)} will execute 
{OR2}. By the way, the program is executed by typing {PLOT-IT} on 
a b/w-monitor and pressing Return.

EXTRAS

In  FORTH DIMENSIONS,  a magazine totally devoted  to  FORTH,  an 
article appeared with the astonishing announcement, that FORTH is 
likely to vanish away as a public known computer-language, due to 
the  FORTH-programmers,  which tend to hide away  this  beautiful 
language  from  the eyes of the world.  In this way,  so  it  was 
written,  they  hope to be the only few people who can make  very 
fast a very fast computer-application. So don't let it happen !
   
EXERCISES

1.  Introducing the word {?THOUSAND},  I told you not to  execute 
    the  definition as it might cause a hang-up.  I also gave you  
    one of the possible reasons:  the returnstack. Now, could you 
    find a solution to this problem by changing the definition  ? 
    You  may change either one or two of two items.  
2.  In which  part of the array {S-D} have been stored the values     
    less than the pivotvalue, left or right  of that value,  when     
    {I'} crossed {I''} for the  first time ? 
3.  We  made  the presumption, that - at a certain moment - {I''}      
    had the value of 139.  What now must have  been  the value of     
    {I'} at the same time ?
4.  Could  you tell me which element served as the second  pivot-
    value, assuming {I''} equals 139 ? 
5.  In which part of a  dictionary-entry of a new word FORTH will     
    compile another,  already existing word,  to  define part  of 
    the  action  of  the new word ?  Is  it  the  linkfield,  the 
    parameterfield or the namefield or none of the three ?
6.  It is  possible to define a word which can view the action of 
    {PLOT-IT} step by step. Write it and call it {STEP} !