May the Forth Be With You

By Dan Azulay

from the January 1984 issue of Electronic Fun with Comouters and Games magazine

How this powerful language stacks up

Those of you who have been driven to desperate acts because you’ve mastered BASIC and feel there is nothing left in life, take heart There’s always FORTH, a very fast, very efficient computer language that is rapidly becoming the language of professional programmers and game designers.

If you’re planning to go to computer camp this summer you may be surprised to learn that in addition to honing your BASIC skills to a fine edge you might be presented with a language you’ve scarcely heard of—FORTH. All the Atari computer camps teach FORTH and many others do as well. One new computer—the Jupiter Ace— even has built-in FORTH Instead of BASIC.

Over 10 years in the making, FORTH still has its supporters and detractors, but it is rapidly gaining in popularity. It’s fast, efficient, and relies on a structure that may be closer to the way a computer ’thinks “than the structure of BASIC.

At the heart of FORTH is a modern innovation in symbolic logic called reverse Polish notation. Symbolic logic was developed around the turn of the century as a way of codifying sentences. Symbolic logic turns sentences into strings of symbols that look a litUe like mathematical equations. Using the symbols instead of the words, it’s easier and more accurate to analyze various steps in an argument to determine whether the conclusion is valid.

A line of reasoning consists of statements (called “propositions”) and connections between them (called “operations”). Given a series of propositions a logician can assign “truth values” to each one. There are only two “truth values”— true or false. There’s no middle ground. If this sounds familiar, it should. It’s a way of reducing reasoning to a binary code — a series of “ons” and “offs” or “ones” and “zeroes”— just like the code that determines what your computer will do.

There are many kinds of notation in symbolic logic, but the one that has become the most popular among serious logicians is reverse Polish notation. Early ways of symbolizing sentences were pretty much strict translations from English. Reverse Polish notation refined symbolic logic to make the symbols easier to manipulate. This is the theory behind FORTH. This accomplishes two things: your programs run faster and they use up less memory than BASIC programs.

This way of organizing data in your computer’s memory also allows it to remember complicated procedures and perform them on command, meaning that you can actually increase your computer’s vocabulary to an infinite degree.

FORTH is an excellent language for video games or for computers which monitor industrial and scientific equipment. In fact, one of the first jobs that FORTH performed for its inventor. Charles Moore, was to control a radio telescope at the Kitt Peak Observatory in Arizona.

Unlike Assembler, and like BASIC, FORTH can be used “interactively”. That is. a FORTH programmer, like a BASIC programmer, can type in commands and have them execute immediately. If your computer runs BASIC you know that you can plug it in. turn it on and type “PRINT 3 + 5”. You will be informed instantly that the result is eight. Similarly, with FORTH on your machine, you can type “3 5 + .” (that’s your reverse Polish notation) and the same reassuring “8” will pop onto your video display.

FORTH gives you this combination of high speed and easy in tion without using very your computer’s memory. Most FORTH systems will run in 8K to 16K of RAM. A Disk-Oriented BASIC Interpreter will often run in that much memory, too. but in order to run Disk BASIC or Pascal, you need to have an “operating system” like CP/M or DOS sitting somewhere in memory as well. This will take up lots of space. FORTH generally contains its own operating system, one much simpler than CP/M or DOS, but effective enough for FORTH to do its stuff.

But the best FORTH feature is language “extensibility”. Computer languages, as you probably know, are essentially a vocabulary of commands that the programmer uses to tell the machine what to do. With most computer languages, the vocabulary is “finite” — you only get a fixed number of commands when you buy the language, and no more. You would no more try to teach your BASIC interpreter to understand a new command than you would try to teach your Buick to dance. With FORTH, you also get a fixed number of commands when you buy the FORTH system. But FORTH’s vocabulary is ultimately infinite. You can teach FORTH as many new words as you like. (If you’re at all familiar with LOGO, you know you can do the same thing with that language.)

You might think: “Why would I want to teach FORTH any new words? Doesn’t it have enough of its own commands to let me write a decent program? I can always get BASIC to do whatever I want with the commands in the BASIC manual!”

True, and you can write FORTH programs with the commands supplied in the FORTH “dictionary” when you first get your FORTH system. What FORTH lets you do is to build new words, new commands, out of the core of commands that FORTH already has in its dictionary. These new commands then go into the dictionary, and are available to use in defining still more powerful commands.

Because of this ability to make up more and more powerful commands, programming in FORTH is something like building a pyramid out of blocks. At the bottom of the pyramid are the blocks (commands) that the FORTH dictionary contained when you bought the system. The programmer then builds the next level of blocks by creating commands for the very simplest and most frequently repeated tasks that the program is going to perform, tasks like moving small images on the video screen or retrieving data from some piece of equipment the computer is hooked up to. Then more words are created to perform more complicated tasks using the simple words already created, and so on, building higher and higher levels of the pyramid, until the commands defined become quite powerful. Finally the programmer defines one word— the top block of the pyramid— which will execute the entire program.

Now that we’ve told you some of FORTH’s strengths— its speed, low memory overhead and language extensibility — it’s time to explain FORTH’s essential peculiarity, the feature FORTH’s detractors are the least happy with. Virtually all operations in FORTH involve something called a “stack “, and while this stack is a powerful and useful thing, it can seem quite strange and confusing to the FORTH novice.

Stacks were around in the computer world long before FORTH ever reared its head, and they are used in almost every computer system, with or without FORTH. FORTH’s stack is only peculiar in that the language depends upon it so completely.

What is a stack? It’s simply a way to store data inside the computer’s memory. In a stack numbers are “stacked up” right on top of each other, in consecutive memory locations. You can think of a data stack as if it’s a stack of anything: plates, books or whatever. Like a real-life stack, a data stack places new numbers on the top. not in the middle or at the bottom. As more and more numbers are added, the stack becomes higher and higher. On most computer stacks, when numbers are to be taken off. they are taken off the top. so that the first numbers to come off the stack are the most recent ones that were put on it. This method of stack organization is often called (for obvious reasons) “last-in-first-out”, or LIFO. FORTH’s stack is a LIFO stack.

As we have said. FORTH uses its stack for almost everything it does. For instance, most computer languages use “variables” to store numbers for arithmetic operations. FORTH also lets you use variables to store numbers, but you can’t use variables directly in arithmetic operations. Instead, numbers have to be taken out of variables and placed on the stack in order to be added, subtracted, multiplied or divided with one another.

For example, the “addition” function in FORTH just adds the top two numbers on the stack. When a programmer tells FORTH to add. FORTH always reacts by adding the very top number on the stack to the number right below it. After the add is complete, both of these numbers will be gone from the stack, “popped” off. as they say. In their place will be the result of the addition, the sum. sitting at the top of the stack.

Likewise, to perform a subtraction operation, the programmer first places two numbers on the stack, then tells FORTH to subtract. The number on the top will be subtracted from the number right below it. both numbers will be popped off, and the result of the subtraction will be “pushed” onto the stack’s summit. This is where reverse Polish notation comes in.

The origin of this term is a reference to the inventor of this form of mathematical notation, the Polish logician Jan Lukaciewicz. Reverse Polish notation is also sometimes called RPN or post-fix notation.

RPN is very different from the arithmetic notation you learned in school. In normal arithmetic notation the “operator” (like + or -) is placed between the numbers to be operated on. For example, the ever popular equation: 2 + 2 = 4

In RPN we place the operator after the numbers to be operated. To arrive at 4 we would write: 2 2 +

In BASIC, which uses standard algebraic notation, the computer will display the result “203” if you type in the following command: PRINT (200*2 + 6)/ 2

To get the same result in FORTH the programmer would have to type in this set of instructions: 200 2 * 6 + 2 / .

This is a post-fix computation of 203. Typing “200” will cause FORTH to put the number 200 on top of its stack. Typing “2” will push the number 2 on top of the 200.

The “*” instruction will cause FORTH to perform its multiplication function, which multiplies the two numbers at the stack top. The 200 and the 2 will now be gone from the stack, and a 400 will be at the top, the result of the multiply command. Then a 6 will be pushed onto the top of the stack, and the " + " instruction will add it to the 400 below it leaving a 406 on the stack, and nothing else. Finally, a 2 will pushed on top of the 406. and the “/” instruction will perform a divide, leaving the result. 203. all alone on the stack. The “.” is a FORTH command that pops the top number off the stack and displays it on the screen. So after typing in the “.” at the end of this calculation, we will see “203”. the result.

Although this may not look like an advantage at face value, it is this unique way of organizing data that allows for FORTH’s real leg-up on other computer languages — extensibility. The computer has such an easy time remembering these stacking procedures that it can duplicate them on command. Instead of filling your programs with GOSUB routines you simply assign a name to your stacking procedure, type in the command, and let the computer do the rest. Each new command can be used as part of a further, more complicated new procedure, which itself can be assigned a name. We can see what a saving this is in computer time andmemory.

Obviously it takes more than numbers and mathematical operations to make up a programming language. FORTH arrives at your door with scores of commands in its dictionary. Here’s a small sample to give you some FORTH flavor.

DUP means duplicate. It tells FORTH to make a copy of the number at the top of the stack, and to push that duplicate on top of the original.

DROP means drop (pop) the number at the top of the stack, making the number underneath it the new top number.

“!” means “store”. It gives you a way to take a number off the stack and put it somewhere else in the computer’s memory. In order to perform a store operation, you have to have the number you want to store sitting at the top of the stack. Then you take the memory “address” of the place where you want the number to go. and push that address on the stack. Once you have those two numbers on the stack— the destination address and the number itself— you perform a “!”.

The two numbers will be popped off the stack and the store will be completed. For example, to store the number 373 at address 4096. you would type: 373 4096 !

“@” means “fetch” a number from memory and put it on the stack. It’s pretty much the reverse of store. To fetch a number you first push its memory address on the stack, then type “@”. The address will be popped off and the number will be pushed in its place.

Using these words we’ve shown you. here’s a series of commands that does something pretty simple. It takes a number from address 1024 in the computer’s memory, multiplies the number times itself (“squares” it), then puts it back again at the same address.

1024 (push the address onto the stack)

@ (pop the address and replace it with the number at 1024)

DUP (make a second copy of the number)

* (multiply the two numbers)

1024 (push the address where the new number is going)

! (store the number)

Let’s get back to the idea of blocks and pyramids and demonstrate FORTH’s famous extensibility by adding something new to the dictionary. Suppose you are writing a program that is going to have to square a lot of numbers, as we’ve just shown you how to do. You certainly wouldn’t want to have to write the same set of commands over and over. In BASIC you might write a subroutine, and GOSUB to it each time you wanted to multiply a number times itself. In FORTH you can do better than that. You can create a new command called “SQUARE”, and execute it each time you have number on the stack you want multiplied by itself. You would define it like this:

: SQUARE (”:” means define. “SQUARE” is the word to define.)

DUP (make a second copy of the number)

* (multiply the two numbers)

; (”;" means end the definition) Once you’ve defined the word SQUARE using the “:” command, you can use it like you use any of the 100 or so operations that FORTH comes with in its original dictionary. The word SQUARE could then replace the third and fourth lines in the program above that fetches, squares and stores numbers. You would write the new program like this:

1024 (push the address onto the stack)

@ (now the number you want to square is at stack-top.)

SQUARE

1024 (push the “destination” address)

! (store the number)

This is just a beginning. New words can be defined that replace entire programs, not just two lines of code. If you’ve understood most of what we’ve told you so far. you’re certainly ready to venture FORTH. There are several books on FORTH,and we can happily recommend at least two: Discover FORTH by Thorn Hogan (Osborne/McGraw-Hill) and FORTH Programming by Leo J. Scanlon (Howard W. Sams and Co. Inc.). Then you can really start pushing, popping and building.