# SECTION F: STACKS IN THE LANGUAGE FORTH

A FORTH statement, and the resulting interaction, is:

`3 4 +  7 OK`

The user types 3 4 + . @ (@ means ''hit the RETURN key''), and FORTH responds 7 OK. (The underlining of the FORTH response is included for visual clarity in the text; it does not appear in actual output.) Table F. I shows the execution of this statement in terms of formal stack operations and SUE.

#### Table F.1

`Token     Response                       Stack S`

`  3       INSERT(S,3)                V1 V2    Vt 3`

`  4       INSERT(S,4)                V1 V2    Vt 3 4`

`  +       begin`

`            Sum  TOP(S)`

`            DELETE(S)                V1 V2    Vt 3`

`            Sum  Sum + TOP(S)`

`            DELETE(S)                V1 V2    Vt`

`            INSERT(S,sum)            V1 V2    Vt 7`

`            end`

`          Write(TOP(S))`

Similarly

`2 3 4 + *  14 OK`

#### Figure F.1

In general, FORTH reads tokens (separated by blank spaces) left to right, stacks operands, and executes words. In this context, arithmetic operators like "*" and "+" are built-in dictionary words. The definition of a word, say neword, is added to the dictionary by simply executing a statement of the form:

`: neword {details of what to do} ; OK`

Here the OK response indicates that a new entry has been put into the dictionary.

Conversion of a length measured in inches to the corresponding length in centimeters can be defined by:

`: intocm 2.54 * ; OK`

This defines intocm to be the sequence of operations:

Push 2.54 onto S.

Multiply the top two values, delete them, and push the product onto S; that is, execute the word "*".

The word intocm may then be used as any other word:

`8 intocm  2032 OK`

If the top value of the stack is 5 (however it got there):

`intocm  127 OK`

Values may be stored in variables as well as on the stack. A variable identifier is bound to a memory cell (declared) when the connection between the two is established. For example

`VARIABLE x OK`

declares x as a variable, and x can then be assigned the value 10 by:

`10 x ! OK`

(The command "!'' is read ''store".) Retrieval of a variable value (to the stack) is done with "@", read "fetch". With the assignment above:

`x @  10 OK`

`x @ intocm  254 OK`

A redefinition of neword does not delete the old definition. When the word neword is encountered in the scan of a statement being interpreted, the latest definition is retrieved. It is possible to back up one definition of neword by execution of:

`FORGE T neword OK`

All dictionary entries made since neword are lost. In effect, the dictionary itself is treated as a stack with respect to the occurrences of a given word within it, as shown in Figure F.2. It is convenient to assume that a word, ''.S'', is available to display the stack contents, nondestructively.

#### Figure F.2

If the stack contains 5 7 2, bottom to top, then:

`S 5 7 2 OK`

A quirk (or astute design choice, if you like) is that access to the top of the FORTH stack is not just a TOP(S) operation but is essentially the operation pair [TOP(S), DELETE(S)], a pop. The use of the top value deletes it. Hence, to square the top value, for example, it is necessary first to duplicate it. A built-in word "DUP" is provided for this purpose. For example, if the stack contains: 5 7 - 2 then:

`S     5  7  -2  OK`

`DUP  S 5  7    -2  -2  OK`

`DUP  *  S  5  7   -2  4`

In terms of formal stack operations, DUP is INSERT(S,TOP(S)).

A number of stack manipulation words are contained in the basic dictionary of a FORTH compiler. The action of some of them is displayed here; their expression in terms of formal stack operations is left to the exercises and problems:

`S 5 7 2 OK`

`/MOD S 5 1 3 OK                       {remainder then quotient, of top`

`{value division of next-to-top`

`S  5 7 2 OK`

`MOD S 5 1 OK                          {remainder of top value division`

`{of next-to-top`

`S   5 7 2 OK`

`SWAP S 5 2 7 OK`

`S  5 7 2 OK`

`DUP  S 5 7 2 2`

`S 5  7 2 OK`

`OVER S 5 7 2 7 OK                     {copy next-to-top and push it`

`S 5 7 2 3 OK`

`ROT S 5 2 3 7 OK                      {cyclic rotation of the`

`{top 3 values`

`S 5  7 2 OK`

`DROP S 5 7 OK`

`S  1  5 7 2 OK`

`2SWAP S 7 2 1 5 OK                    {swaps top pairs`

`S 5  7 2 OK`

`2DUP S 5 7 2 7 2 OK                   {duplicates top pair`

`S  5  7 2 3 4 OK`

`20VER S 5 7 2 3 4 7 2 OK              {copies second pair`

`{and pushes it`

`S  5  7 2 OK`

`2DROP S 5 OK                          {discards the top pair`

Exercise EF.1 and problem PF.1 are appropriate at this point.

## F.1 FORTH Control Structures

The heart of any procedural language is the set of control structures it provides. It is necessary to have conditional branch statements in a language, and it is very awkward to do without explicit loops. Some peculiarities of control statements in FORTH are created by the way in which words are dealt with sequentially, in conjunction with an operation on the stack.

Everything in FORTH is postfix and stack-related, but the necessary structures are provided. For example

`: Checkten 10 = IF Powwow THEN; OK`

adds a word to the dictionary, which--when executed--plays the same role in program logic as the SUE statement

`if TOP(S) = 10`

`then Powwow`

`endif`

but it differs because it also manipulates the stack. A partial trace of its action is shown in Table F.2.

#### Table F.2

`token        operation`

` 10          INSERT(S, 10)`

`  =          begin`

`               t1  TOP(S)`

`               DELETE(S)`

`               t2  TOP(S)`

`               DELETE(S)`

`               if t1 = t2`

`                   then INSERT(S,1)     {any value but 0 is`

`                   else INSERT(S,0)     {considered to be TRUE`

`                   endif`

`                 end`

`  IF           bool  TOP(S)`

`               DELETE(S)`

`               {The decision to execute or not to execute Powwow`

`               {is then, in effect,`

`               {if bool then Powwow endif`

Similarly

`: Spliten 10 = IF Powwow ELSE Wait THEN ; OK`

adds a word to the dictionary, which--when executed--plays the role of the SUE statement:

`if TOP(S) = 10`

`then Powwow`

`else Wait`

`endif`

Problem PF.2 and program PGF.1 are appropriate at this point.

Loop structures in FORTH are only slightly more complex.

A DO-loop is specified in FORTH by:

`: DEF {limit} {index} DO {what you will} LOOP;`

One such loop definition is:

`:echo 5 to 1 DO . "shout " LOOP ; OK`

When executed:

`echo shout shout shout shout shout OK`

The index of the DO-loop is accessed within the loop by the FORTH word "I". With the help of the FORTH word "CR" that prints a carriage return:

`: echo2 3 to 1 DO CR . "shout " I LOOP ; OK`

`echo2`

`shout 1`

`shout 2`

`shout 3 OK`

Exercise EF.2 and Problem PF.3 are appropriate at this point.

Additional features of FORTH are described in [BRODIE, 1981] and [BYTE, 1980],

## Exercises

Exercises immediate applications of the text material

`MOD, /MOD, SWAP, DUP, DROP, OVER, 2DROP`

`:mystery 10 1 DO I * LOOP;`

## Problems

Problems not immediate, but requiring no major extensions of the text

`ROT , 2SWAP , 2DUP , 2OVER`

PF.3 Choose one of the example problems EP2. 1-EP2.5 of Chapter 2.1. Write a sequence of variable definitions and FORTH dictionary words with the property that the final word in the sequence solves the problem.

## Programs

Programs for trying it yourself