This description is copyright 1993 by ACM, and was developedfor the Second History of Programming Languages Conference(HOPL-II), Boston MA.
Philip J. Koopman, Jr.
koopman@cs.cmu.eduForth is both an extensible language and an interactiveprogram development methodology. Originally developed forsmall embedded control mini- and micro-computers, Forthseems to have been implemented on every major processormanufactured. It has been used in a wide variety ofapplications, including spreadsheets, expert systems, multi-user databases, and distributed real time control systems.
At the most superficial level, Forth is a directlyexecutable language for a stack-based abstract machine. Inits essential form, the Forth abstract machine has a programcounter, memory, ALU, data evaluation pushdown stack, andsubroutine return address pushdown stack.
Data evaluation in Forth is accomplished on the DataStack using Reverse Polish Notation (RPN), also calledpostfix notation. For example, the following sequence typedfrom the keyboard: 3 4 + 5 * . 35 ok
interactively pushes the value 3 on the stack, pushes thevalue 4 on top of the 3, destructively adds 3 and 4 to get7, then multiplies by 5. The . operation displays thesingle resultant top value on the stack, 35 (computer outputis underlined). ok is the Forth command prompt.Operations such as SWAP and DUP (duplicate) reorder andreplicate the top few Data Stack elements.
At a deeper level, Forth programs use RPN not as an endin itself, but rather as a means to achieve simple syntaxand flexible modularity. Small, simple programs to performcomplex functions are written by reusing common codesequences through a programming practice known as factoring.
Subroutine calls and returns are an important part ofForth programs and the factoring process. As an example,consider the following function (called a word in Forth)which computes the sum of squares of two integers on top ofthe Data Stack and returns the result on the Data Stack:: SUM-OF-SQUARES ( a b -- c ) DUP * SWAP DUP * + ;
The Data Stack inputs to the word at run-time are twointegers a and b. The Data Stack output is a single integerc. The : denotes a function definition with the nameSUM-OF-SQUARES. The ; terminates the definition. Comments areenclosed in parentheses. This example follows the Forthconvention of including a stack-effect comment showing thata (the second stack element) and b (the top stack element)are consumed as stack inputs, with c produced as the stackoutput.
By the process of factoring, the example program wouldbe re-written in Forth using a new definition (a factor)called SQUARED to allow sharing the common function ofduplicating and multiplying a number on the Data Stack. Theseparation of the Return Stack from the Data Stack in theabstract machine allows the values on the Data Stack to becleanly passed down through multiple levels of subroutinecalls without run-time overhead. In this new version, DataStack elements are implicitly passed as parameters from SUM-OF-SQUARES to SQUARED:: SQUARED ( n -- nsquared ) DUP * ;: SUM-OF-SQUARES ( a b -- c ) SQUARED SWAP SQUARED + ;
Good Forth programmers strive to write programscontaining very short (often one-line), well-named worddefinitions and reused factored code segments. The abilityto pick just the right name for a word is a prized talent.Factoring is so important that it is common for a Forthprogram to have more subroutine calls than stack operations.Factoring also simplifies speed optimization via replacingcommonly used factors with assembly language definitions.In the preceding example, SQUARED could be re-written inassembly language for speed while maintaining the same stackeffects.
Writing a Forth program is equivalent to extending thelanguage to include all functions needed to implement anapplication. Therefore, programming in Forth may be thoughtof as creating an application-specific language extension.This paradigm, when coupled with a very quickedit/compile/test cycle, seems to significantly increaseproductivity. As each Forth word is written, it can betested from the keyboard for immediate programmer feedback.For example, the definitions above could be summarily testedwith:3 SQUARED . 9 ok3 4 SUM-OF-SQUARES . 25 ok
Forth systems use two levels of interpretation: a textinterpreter and an address interpreter. When acceptingkeyboard or file-based input, the text interpreter extractswhitespace-separated character strings. In interpretationmode it attempts to execute the corresponding words (numericinput is trapped and converted as a special case). : is aword like any other, but creates a new dictionary entrycontaining the word name (symbol) and places the textinterpreter into compilation mode. While in compilationmode, most words extracted from the input stream arecompiled into a pointer to the word's definition in thedictionary instead of being executed.
A compiled Forth program is a collection of words, eachof which contains a statically allocated list of pointers toother words. Ultimately the pointers lead to assemblylanguage primitives, some of which may be user-written. The Forth address interpreter is used to executecompiled words, classically using threaded code techniques.The Forth text interpreter, while not used in executingcompiled programs, is often included in applications as thebasis of a command-line user interface.
Forth systems use one-pass compilation. There is noexplicit Forth parser (and, for practical purposes, noformal grammar). Control flow words have a specialimmediate attribute, and are executed immediately even whenthe text interpreter is in compilation mode. Immediatewords, when executed, typically cause compilation of specialstructures. For example, IF compiles a branch conditionalupon the top runtime Data Stack value, and the matching THEN(the "endif" word) back-patches the branch target address.Users can readily create their own immediate words, thusextending the compiler by adding new control flow structuresor other language features.
Data structures are created by another special class ofwords: defining words. Defining words have two parts: theCREATE clause creates the dictionary entry for the datastructure instance, while the DOES> clause is a definitionshared by all data structures created by that defining word.For example, an array defining word creates a named arrayand reserves storage with its CREATE clause, then computes anaddress (given indices on the data stack) with its DOES> clause. Defining words are commonly used to hide data structure implementations and to create families of similar words.
Forth programmers traditionally value completeunderstanding and control over the machine and theirprogramming environment. Therefore, what Forth compilersdon't do reveals something about the language and its use.Type checking, macro preprocessing, common subexpressionelimination, and other traditional compiler services arefeasible, but usually not included in Forth compilers.This simplicity allows Forth development systems to be smallenough to fit in the on-chip ROM of an 8-bitmicrocontroller. On the other hand, Forth's extensibilityallows "full-featured" systems to consume over 100K bytesand provide comprehensive window-based programmingenvironments. Forth also allows (and often encourages)programmers to completely understand the entire compiler andrun-time system. Forth supports extremely flexible andproductive application development while making ultimatecontrol of both the language and hardware easily attainable.
Philip J. Koopman Jr.
ACM Copyright Notice:
Permission to copy without fee all or part of this materialis granted, provided that the copies are not made ordistributed for direct commercial advantage, the ACMcopyright notice and the title of the publication and itsdata appear, and notice is given that copying is bypermission of the Association for Computing Machinery. Tocopy otherwise, or to republish, requires a fee and/orspecific permission.
Phil Koopman --