FORTH: A Stack Programming LanguageHarley WittRussell LewisMay 14th, 2008Introduction:Forth is stack based programming language and therefore uses postfix notation. It is composed of numbers and words. In the following statement which adds 1 and 2, “1” and “2” are numbers and “+” is a word. 1 2 + The language is interactive and therefore as the user enters “1 2 +” and then hits the enter key, the program begins to interpret left to right, top to bottom. “1” is pushed on the the stack, followed by “2”. Then the “+” is looked up in the dictionary and this function is carried out. The “+” word will take the top two items in the stack, add them and then push the result onto the stack. At this point since “1” and “2” were removed off the stack, the result “3” is at the top of the stack.Let's examine another simple example to multiply the number 5 by itself (5 * 5) as follows:5 DUP *“5” is pushed onto the stack, then DUP is looked up and executes its function which copies the topmost element on the stack and pushes the result onto the stack. “*” then pops the top 2 elements, multiplies them and pushes the result onto the stack which would be “25”.The final simple example is a function to determine the absolute value of an item on the stack. This could otherwise be expressed as (i<0) ? -i:iDUP 0 < IF -1 * THENLet's assume -3 is the top item on the stack. “DUP” will push another -3 onto the stack. “0” gets pushed onto the stack. “<” is looked up and pops 2 elements from the stack (0 and -3), compares them and pushes that resulting boolean value (“T”) onto the stack. “IF” is looked up and pops the “T” from the stack, since the value is “T” the interpreter continues. “-1” is pushed onto the stack. “*” is looked up and pops two items off the stack (-3 and -1), multiplies them and pops the result “3” onto the stack. “THEN” is looked up and no operation is performed. We therefore see the result of and absolute value function that turned the element “-3” into a “3” at the top of the stack.History:In the 1960s Charles (Chuck) H. Moore(1) was a scientist working on programming languages such as ALGOL and FORTRAN at MIT and the Stanford Linear Accelerator Center. He felt too much time was spent writing, compiling and running code. He focused his efforts on coming up with a solution to create a text interpreter (written in ALGOL) which was run in an interactive mode and acted upon items that were either numbers or words. This combined the steps of edit, compile and run into command line level interpretation and compilation. Special words were created such as the “:” to mark the beginning of code that should switch the interpreter into compile mode and “;” to mark the switch back to interpreter mode. When such a “:” <name> ... “;” block was encountered the compiler would store the “word” (we would call it a function) into the dictionary for later use during interpreter mode. Writing code utilizing two stacks (one for temporary values and parameters, one for stack frames) and simple dictionary allowed the code size to be compact, efficient and extensible.In 1970 while working on an IBM 3rd generation computer, he felt as if the language he was writing was a fourth generation language. As the computer only allowed for 5 character names, the result was to name the language “FORTH.” The first public version of FORTH was used at the National Radio Astronomy Observatory in Arizona in 1971. The program was used for data acquisition and analysis as well as concurrently controlling the radio telescope. The popularity of the language quickly spread within the Astronomy community. He later spawned initiatives to further promote the FORTH language and many different versions of FORTH were created. MiniFORTH and MicroFORTH were used in minicomputers and micro controllers. The compact size of the programming language images continues to provide value in boot loaders today.Applications:FORTH is a strange beast. An imperative, stack-based language, FORTH combines low-level computational capabilities with a remarkably powerful function declaration mechanism. The former allows FORTH programs, when compiled by an optimizing compiler, to run nearly as fast as hand-optimized assembly; the latter allows a FORTH program to literally rewrite the compiler as the program is being compiled and executed.Because of these two very different strengths, FORTH is used in two very different classes of applications. When an aggressive optimizing compiler is available, FORTH can be useful as a powerful numerical processing language. On the other end of the spectrum, FORTH is useful in embedded systems, on prototype hardware, or as a boot loader, because only the most minimal compiler kernel is required; once a FORTH compiler kernel is available, a fully-functional FORTH compiler can literally be built on the fly using only the FORTH language itself.Analysis:The basic FORTH language is essentially a portable wrapper around assembly language, plus the basic mechanisms needed to allow compiler self-modification. FORTH provides just enough abstraction to allow for a type of "structured assembly language;" or, with effort, the function-declaration mechanism can be used to build a complete suite of higher-level language constructs, including a variety of loop types, if/then/else statements, and even function pointers.However, while FORTH allows for the construction of extremely complex control structures, it does not appear that FORTH has any significant capability to implement complex memory structures. (If it is possible, the "authoritative book" on FORTH makes no mention of it.) FORTH's memory management is painful in the extreme and astonishingly primitive. The only native storage mechanisms are for single- or double-word values (usually integers); to construct anything as simple as an array, one must allocate a variable and then increment an internal pointer in the dictionary to allocate more space. (Thus, an array in FORTH is simply a region of undocumented memory.) Presumably, records could be created in a similar fashion, but FORTH provides no standard, reliable mechanisms for indexing arrays or accessing member fields. FORTH expects you to simply calculate the indices yourself and increment pointers, just as in typical assembly language programs.Moreover, FORTH