Forth - Waikato Linux Users Group

`YOU FORTH LOVE IF HONK THEN`

Forth is a Stack-based ProgrammingLanguage developed by ChuckMoore in the 1960s (see the Evolution of Forth). Forth code is written in ReversePolish notation, since it works directly with the stack (actually, several stacks). There is no implicit stack management, which means that function calls are very fast: the arguments are whatever is already on the Stack when the function is called and the return value is whatever is left on the Stack at return.

Forth is defined in terms of itself more so than probably any other language. A Forth system generally consists of only a tiny kernel and a small number of Forth functions written in AssemblyLanguage, but even most of the compiler is written in Forth, as is the standard library. Real Forth geeks write their own Forth kernels from the metal up. (ChuckMoore creates his own Forth machines from silicon.) It doesn't take much effort once you've absorbed the Forth philosophy – there is shockingly little holding Forth up. This is in tune with ChuckMoore's philosophy of brutal simplicity in software engineering.

Forth produces very compact code. A whole interpreter and development system will easily fit into 8 kilobytes and leave plenty of room for user code. Back when architectures with 8 kilobytes of RAM weren't just the computers that you developed for but also the computers you developed on, Forth was very popular. Today it is most popular in embedded systems and other highly constrained environments: f.ex., it is the language of choice for NASA on many satellites and planetary probes, where its compactness and functional correctness (see below in Comparison with Haskell) outweigh the speed of AssemblyLanguage. It forms the basis for the OpenFirmware and the RPL language used in HewlettPackard calculators and is used in some of UCSD's music courses. It has been used successfully in ArtificialIntelligence research.

Concepts

This is a general description of how Forth works. It's different. If you like Brainf*ck you will like Forth.

Forth functions are called words. They are organised in the user dictionary.

A Forth machine has two stacks. When subroutines (called words in Forth lingo) are called they pop arguments off the parameter stack and push back return values. The return stack holds the return addresses of word calls.

Finally, the input buffer for the Forth parser forms an integral part of a Forth system.

Words manipulate the parameter stack directly to perform calculations on their arguments and leave return values. Traditionally, there are no local variables in Forth (but there are global variables, which are simply pointers stored under a name in the dictionary): the parameter stack is used for all temporary storage. There are lots of words for many simple stack manipulations, such as pushing another copy of the top-most value, dropping it, rotating the stack in either direction, rotating part of the stack, etc. Programming in Forth means keeping track of what is supposed to be on the stack at any point.

The dictionary is also structured like a stack. As words are defined, they are added to the top of the stack. You can recycle memory by forgetting, which means dropping all the entries at the top of the dictionary down to some word you specify (usually you do this implicitly by executing a word defined using MARKER). Sets of words are usually loaded/defined as a unit, and are usually referred to as a vocabulary, analogous to libraries in other languages. The first vocabulary is a tiny kernel of word definitions written in MachineCode, then there is a standard library vocabulary defined in Forth, and then optional vocabularies that define a simple text editor, assembler and disk OperatingSystem. (A modern Forth system might have a TCP /IP stack on there somewhere too.) Some Forths permit multiple vocabularies to exist concurrently and independently, thus providing namespaces.

The word : tells Forth to begin compiling the subsequent words found on the input buffer, and the word ; then tells it to stop. You use : to add new words to the Forth system until you've created a high-level Forth vocabulary that you can easily express your problem in. You just keep going until you've defined a single word that, when called, executes your entire program. Forth is very much a BottomUp language. :-)

Most words compile to call statements. Words that look like integers compile to push statements. Some words, however, have flags that tell Forth to execute them immediately while compiling: these create control structures in the ByteCode of a word, affect parsing, or perform other compiler or macro functions.

There is no syntax in Forth, just words that manipulate other words and the input buffer and user dictionary.

Examples

Sentences long extremely and notation Polish reverse in writing about wrong is what?
— Jarkko Hietaniemi

The following code is a simple text editor from Retro Native Forth:

0 variable lastBlock
asmbase $1024 + constant blockBase

: block         512 * blockBase + ;
: select        dup lastBlock ! ;
: vl            dup 40 type cr 40 + ;
: view          lastBlock @ block vl vl vl vl vl vl vl vl vl vl vl vl ;
: edit          select block s drop drop view ;
: delete        select block 512 0 fill view ;
: edit-line     40 * lastBlock @ block + s drop drop view ;
: delete-line   40 * lastBlock @ block + 37 0 fill view ;

This demonstrates the preferred programming style in Forth: short words laid out mostly horizontally, just like words in a college dictionary.

The next example is a utility word from the IRC bot in ISForth.

\ receive up to 512 bytes from bot socket

: bot-read
  off> #inbuff
  inbuff                \ where to receive into
  begin
    1 over bot-fd recv  \ read one char from bot socket
    1-                  \ result should be 0 now
    if                  \ if its not then we didnt get any input
      drop exit         \ so discard buffer address and exit
    then
    incr> #inbuff       \ we got a character
    dup c@              \ get the character we just read
    $0a <>              \ while its not an eol
    #inbuff 512 <> and
  while
    1+                  \ advance buffer address
  repeat
  drop                  \ discard buffer address
;

This is a single long word, written with a predominantly vertical layout. Such code is hard to read (eg. the while loop's condition check consists of the overwhelming bulk of the code), and is considered poor style.

For an almost poetic example of Forth, see LifeInForth.

Optimisations

Contemporary Forth systems are much more complex than naïve interpreters in order to avoid spending a lot of time executing call statements and to reduce the overhead of interpretation.

Instead of compiling words to call statements, they might be inlined, even as MachineCode instructions embedded in the ByteCode so the target CPU can execute them directly. One form of this is called subroutine threading. Since many target architectures are register-based, numeric literals might be embedded as immediate operands in MachineCode instructions.

Optimising compilers will wait before putting anything in the dictionary until they encounter the ; word, rather than building the definition piece-meal in the dictionary. They can then perform proper lexical analysis and parsing to help generate efficient code. Some highly optimizing compilers will even infer types based on the words called in a word!

Comparison with Haskell

There are many similarities between Forth and functional programming languages. For example, this is the definition of block from the first example

: block    512 * blockBase + ;

This can be likened to the more traditional functional style

let block b = blockBase + ( 512 * b )

The similarities go far deeper though, and there are many deep dualities.

Haskell compiles software to a tree of closures – bundles of code and data that together form a function in the mathematical sense. In Forth, because parameters are placed on the stack, there is no need to store free or bound variables in the program structure. Hence, a poiner to a closure consists only of its code pointer; therefore, typical "threaded" Forth code maps 1:1 to Haskell's closure-based code.

The fact that bigFORTH and the Glasgow Haskell Compiler produce binaries that are about equally performant is no coincidence.
Forth has issues using local variables, but can maintain global state with ease. Haskell has issues using global state, but can maintain local variables with ease. To address these issues, ANSI Forth introduced a portable locals wordset, while Haskell uses monads to deal with global state. Both constructs are fully expressable in the core language, and both address (essentially) different sides of the same problem.
Forth allows the compiler to be extended by fundamentally altering the compiler in terms of words written in the base language itself. Haskell utilizes monads for this same purpose.
Haskell uses the >>= operator to compose the right-hand monadic function onto the results returned by the left-hand computation. Save for the threading of state this is normal function composition. In Forth, which is described mathematically as a purely combinator-based language, composition is performed by concatenation – e.g., simply listing one word after another. Hence, both Forth and Haskell code can be expressed via function composition, and therefore, reasoned about algebraically.
Forth allows one to freely alter the return stack. Return stack items are (usually) return addresses ie. (partial) continuations. Freely altering the return stack is dangerous and can produce unstable software. However, there are nonetheless distinct patterns of return stack manipulations you can use to produce extremely compact representations of fairly high-level control flow structures. This introduces the concept of "return conventions," as distinct from "calling conventions." It turns out that Haskell uses return conventions as well, under the hood, to optimize pattern matching in case and function evaluation.

YOU FORTH LOVE IF HONK THEN

Concepts

Examples

Optimisations

Comparison with Haskell

See Also

`YOU FORTH LOVE IF HONK THEN`