The simplicity of the Forth language makes it easy to not only extend the language into a tongue that is perfectly suited to a particular problem but rewrite the language from the ground up as you see fit. It is a language the encourages experimentation with problems, thought, and the language itself.
The language was first developed by Charles Moore around 1968 by his recollection. The language has changed over the years as one can see if one compares the first paper published on Forth FORTH - A Language for Interactive Computing from 1970 with modern Forths.
The Forth Interest Group is a non-profit organization to support the Forth programming language and Forth community. They offer a number of public domain Forth systems and some with meta compilers. However I was not aware of any web pages that attempt to explain Forth meta compilation so I decided to create this one.
I had used Forth meta compilers for years without needing to understand what they were really doing. All I needed to know whas that I could simply edit the source code to these Forth systems and generate a whole new Forth system. I only began to understand what a meta compiler really does when I wrote one. I gave a couple of talks to FIG about these compilers and put some information about them at my web site but previously I had only some text documents here about meta compilation. I began by creating html versions of a couple of old documents. A Simple Meta Compiler and A One Word Meta Compiler were my first attempts to explain meta compilation.
This document will provide some prerequisite information and try to give an overview of the subject. Hopefully it will demystify the subject for some people.
The normal operation of Forth is to act as both an interpretter and a compiler. It is a command interpretter because it can accept commands, look them up in a dictionary, and execute them by name. It can also act as a compiler by creating new executable programs or new named commands. To be able to use the language one only needs to understand a few concepts. One must first understand that a Forth virtual machine uses stacks, and that it has two of them. There is one stack that holds temporary data and one stack that holds program return addresses. There language is defined by a set of named operations on those stacks and some named operations to create new named operations.
The user of Forth often does not need to understand the inner details of their compiler. If they wish to modify the inner workings of their Forth or meta compile a new and different Forth, or write their own Forth from scratch they will need to understand some of the inner details of their Forth system.
The normal Forth system contains layers of code starting with code that implements the Forth virtual machine. The next layer of code usually supports the name and code dictionaries and a minimal compiler and interpreter. The following layers usually contain additional functions. This is the way the ANS Forth standard is organized. There is a small set of words called the CORE that are the minimal set needed to define a system that conforms to the standard, and there are additional sets of standard Forth defintions for standard extensions to the basic core of the language.
This type of design can simplify the compilation of a new Forth system because once you have a system that supports the CORE wordset it can compile code. So all you need to do is compile the core of a new system and it can then compile extensions to its core itself. This is the normal operation of Forth.
In the normal Forth system one compiles application code on top of the Forth system itself using its compiler. The application becomes an extension of Forth. The application itself becomes a named command in the new language. The programmers developing code simply saves the system from time to time. It will include the new words they have added. There is no clear distinction between the Forth system, its compiler, and the application.
An Application Combined with a Normal Forth System
Forth virtual machine
In the traditional Forth system there is usually the option to turnkey the application so that a sealed application will boot up and go directly to the application code. It may or may not include the Forth compiler or command interpreter as part of the application.
Some Forth systems offer the ability to remove the names or headers from the words in the system when sealing it up as a turnkey application. Other Forth systems offer the ability to compile a stand alone turnkey application that does not include any of the Forth compiler code itself. I like to use the term target compiler for this type of compilation.
A Forth Target Compiler and Application
Program 1: Application code
Program 2: Forth extensions
Forth virtual machine
A target compiler produces an application program that is separate from the compiler. In Forth we call this a target compiler, but it the way most compilers work in other languages.
If the target application code contains a Forth system then it is a special class of target compiler. When a Forth compiles a new Forth we call it a meta compiler.
Meta compilers represent a more complex problem than target compilers because a target application will just be made up of new words while a target Forth system will be made up of words of a new set of Forth words. A meta compiler will have to deal with two sets of Forth words at the same time.
There are many different models used to implement Forth such as Indirect Threaded, Direct Threaded, Subroutine Threaded, Native Code, Tokenized, and Bit Threaded. There are many different machines and operating systems and target environments. And of course there are many different Forth meta compilers.
The target (for the target or meta compiler) may or may not use the same Forth model, and may or may not be for the same machine or OS. This is the main difference between a normal Forth compiler and a Forth meta compiler. Also a meta compiler must deal with two Forths at once.
The terms that I use in this document are:
Forth Compiler compiles application code into a Forth system.
Target Compiler compiles a separate stand alone application.
Meta Compiler compiles a separate new Forth system.
Clone Compiler compiles a separate new Forth system for the same model and same machine.
From these definitions it is clear that all Clone Compilers are Meta Compilers, and that all Meta Compilers are Target Compilers.
If we have a word called X that does something and another word called Y that does something else we can compile a new word, call it Z, that does X and then Y by saying
: Z X Y ;The : starts compiling and takes the next name as the name of the new word. Then the words X and Y get compiled into the defintion. Finally ; ends the word, stops compiling, and switches back to interpretation.
Most Forth words do different things whey they appear inside of a definition or outside of a defintion. That is when they appear between : and ; they get compiled and if they don't appear between those words they get executed.
We can define a word that prints out 123 in may ways. We could say
: 123. ." 123" ;In a Forth system this defines a new word named 123. that will print out the string 123 if executed. If you type 123. in such a system it will respond by executing that defintion and printing out 123. However if this word appears inside of another definition then the word will be compiled into the new word. Instead of printing out the 123 at the time it is encountered it would add that functionality to the word being defined and one of the things it will do when it is executed is to print out 123.
So now if we say
: DEMO 123. 123. 123. ;We will not see 123 being printed out while DEMO is being defined. We would however see it printed out three times if the word DEMO is executed.
There are some words in Forth however that don't get compiled inside of a Forth definition. We call these words IMMEDIATE. When wcompiling these words don't get compiled, they get executed immediately instead. We have already seen one of these words even though we have only seen two words so far. The ; above is an IMMEDIATE word because unlike our 123. it must do something besides simply compiling one definition into a new word, it will also stop the compilation.
Ok, so we have established that when compiling new words a Forth compiler compiles most words and executes IMMEDIATE words.
Lets look at those two things in more detail. How does a Forth compiler actually compile most of those words?
How a Forth compiler actually compiles a normal Forth word depends on the type of compiler. If it is threaded Forth (Direct, Indirect, or Bit threaded) it compiles an execution token that is normally nothing more than the execution address of the Forth word. In threaded Forth most words are mostly just lists of addresses of other words.
In a tokenized Forth the tokens that get compiled may be smaller than addresses and may be indexes into a table of functions, or predefined functions. The most common tokenized Forth is the boot language on SUN workstations. Open Firmware has also been adopted as the language for implementing portable BIOS code for cards on several new busses. SPARC, PowerPC, and Intel x86 microprocessors will be booting up in Forth on many systems being developed today. For more information look into FirmWorks. Sun offers the Open Firmware Home Page. These tokenized Forths compile 8 bit tokens.
In subroutine threaded or native code Forth compiles the compiler compiles words by compiling a subroutine call or some inlines machine code rather than an address or a token.
Some Forth compilers also implement some optimizations on the compiled code. Some of these optimizations may be done on any Forth system while others take advantage of things are that specific to a particular model or processor.
To understand a Forth compiler one must also understand what sorts of things those IMMEDIATE words do. Lets examine the word IF. Lets begin with a simple example.
: DEMO IF X THEN Y ;
In that example the word DEMO is defined. The defintion begins with the word IF. The meaning of the IF is that the new word should execute the words that follow the IF only if the top of the stack is not zero, otherwise it execution should continue after the THEN. To accomplish this the word IF is IMMEDIATE and will execute when it is encountered inside of the defintion. When it executes it compiles code to do a conditional branch. As discussed before the way it actually compiles this code depends on the Forth model. The code that will be compiled by the IF is a piece of runtime code sometimes called 0BRANCH. It could be given almost any name, but it is a word that tests the top of the stack for zero and branches if the top of stack is zero. It will branch past the compiled code that comes after it if the top of stack is zero or it will continue on to the compiled code that comes after it if the top of stack is not zero. At the time that the IF executes the address it will branch to is not known so it actually compiles an unresolved forward branch. When the THEN is encountered in the source code it is an IMMEDIATE word and resoves the address in the IF branch with the proper destination. I n this case it would resolve the conditional jump before the X to after the X and before the Y.
It is clear that IF and THEN are not simply compiled like the X and Y they are executed immediately to compile some primitive operation and do some other things.
The Forth compiler will construct two dictionaries, one for names and one for code. The name dictionary is often a linked list, but it could also use a hash table or some other mechanism for searching the list of names. The compiler or interpreter search through the list of names to get the execution token for a Forth word. The name and code dictionaries may be mixed together, or they may be in separate locations in memory.
Forth provides mechanisms for managing more than one list or words. These are called word lists in ANS Forth and vocabularies in older Forths. This provides a way for a single name to exist in several different places and for each version to have different code attached to it. The programmer can choose the meaning for the word by specifying which word list to search first to find the version of a word that they want.
Although size is generally related to complexity they are not the same thing. A larger Forth system has more potential for complexity because there are more places for complexity to hide but it is possible that a small Forth system could be very complex and that a large Forth system could be very simple in its structure.
Generally threaded Forths have a simpler implementation model than subroutine threaded or native code Forths. In threaded Forths most of the definitions are little more than address lists. In these Forths there is often a clear and simple relationship between the source code description and the compiled lists of addresses. For this reason decompilers for these Forths are quite simple. For native code compilers or compilers with optimizations there may not be such a clear and simple relationship between source and object code.
Feature rich Forths tend to be more complex than Forths that have fewer features. But just as with size the implementation of those features is more important than the number of features. A system can be large and have many features but if those features are created with only a few simple constructs the overall complexity may be less than a smaller Forth with fewer features but where more variety of implementation techniques are used to build the features that are there.
Some criteria for judging the complexity of a Forth:
How many words are implemented in CODE?
How complex is the assembler in this implementation?
The minimal assembler is , that is the Forth word COMMA stores a value into memory. The minimal assembler is no assembler at all, simply store the numbers for the target opcodes into memory, machine code.
The number of opcodes, the number of addressing modes, the depth of the pipelines, and the use of caches all contribute to the overall complexity of the assembler portion of a Forth system if it uses an assembler. The real issue is how complex is the target processor and the target implementation. If the implementation only has a few words in assembler and these words are short one may understand the code without having to understand everything about the target machine. If an implementation is well tuned to a particular machine then an understanding of the code and the design of the implementation will require a more in depth knowledge of the target machine.
What flow control structures are used in this implementation?
How many IMMEDIATE words are there in this implementation?
When Chuck designed cmForth he knew that the target hardware supported a count down loop in hardware and so he implemented a FOR NEXT construct. This was a simpler approach than the traditional DO LOOP (?DO +LOOP) approach and it mapped better to the hardware on the Novix.
As noted earlier most words in Forth are not IMMEDIATE and are simply compiled when encountered inside of a definition. All words that must have some immediate action when compiling must be given special definitions that specify what they will do when executed at compile time. For instance the word IF will compile a primitive sometimes called 0BRANCH and leave the address of the unresolved forward reference to be resolved later by some other word. It may also do other things like implement compiler security or optimizations.
The kernel of Forth systems that implement things up to the working CORE compiler is the minimal amount of code that a meta compiler must compiler in order to have a working target Forth system. Once you have such a system it may be expanded to any level of complexity with its own compiler. The meta compiler may therefore only have to deal with the source for a simple kernel or a more complex kernel and/or a target application.
Bill Muench designed the original eForth 1.0 for simplicity and portability. It had only 30 words written in assembler and used only BEGIN_UNTIL BEGIN_WHILE_REPEAT IF_ELSE_THEN and FOR_NEXT in its source. The second release reduced the number of code words to 28 and removed the FOR_NEXT constructs from the source code and replaced them with BEGIN constructs. I was pleased to learn this when I was designing a meta compiler to generate a version of eForth for a new target. It meant that there were fewer IMMEDIATE words that were needed in the meta compiler. The meta compiler no longer needed to compile FOR_NEXT constructs.
Does this implementation of Forth support wordlists?
Does this implementation of Forth use CREATE DOES> in its source?
Does this implementation support multitasking?
Does this implementation support code optimization?
The inner loop of a simple Forth compiler simply checks if a word is in the dictionary and if it is it checks if it is IMMEDIATE. If it is IMMEDIATE it executes it and if it is not then it simply compiles a Code Field Address. If the word is not in the dictionary it either converts it into a number or generates an error.
Usually a Forth meta compiler is more complex than a normal Forth compiler. It will have two sets of dictionaries to deal with, the host name and code dictionaries and the target name and code dictionaries. Sometimes there may be no target name dictionary. Sometimes there are other dictionaries and wordlists involved as well.
There are a number of other reasons for complexity that don't apply to normal Forth compiling. When compiling a Forth for a target system there are some problems that just don't appear when you are compiling executable code on top of a running Forth. (see Fig. 1)
Do the host and target machines have the same width bus?
Do the host and target machines use the same representation on the bus?
When target or meta compiling if the host and target machines don't use the same representation on the bus then some logical operation is needed when moving data from the host to the target. When moving from a positive to a negative bus machine or visaversa one must XOR with all 1s. (FF XOR all bytes)
Chuck's MISC computers use a third representation on the bus. In these machines even and odd bits use alternate positive and negative bus logic. This applies to both the data and address busses on these machines. As a result when target or meta compiling for these machines from a PC one must XOR both data and addresses with AAAAA.
Having to change the representation of data or addresses is not a problem that appears in normal Forth compiling nor does it apply to target or meta compiling when the target machine uses the same physical representation for logic on the bus. This is not a problem for clone compilers.
Will the host assembler generate machine code for the target?
Will the target code be executable on the host compiler?
A meta compiler that includes a target simulator will be able to simulate execution of target words including words written in the target assembler. This will add some degree of complexity to the meta compiler.
Some target or meta compilers use an umbilical connection between two machines. These are sometimes called tethered systems. In these configurations the host machine may request execution of target code on the target machine. The system may act as if a normal Forth compiler was running on the target system with full freedom to interpret and incrementally compile target code. In fact their may be no Forth compiler on the target system and the compiler can reside on the host system but appear to user as if it were running on the target system.
Will the target Forth be created at the address where it runs?
Even if the target is a different machine will the meta compiler also produce a second version of the target system code that can be executed on the host meta compiler?
Does this implementation of Forth use CREATE DOES> in its source?
How many targets will the meta compiler support?
How many optimizations will the meta compiler support?
Does the system depart from the traditional way of meta compiling?
When the subject of cmForth came up in the comp.lang.forth newsgroup on the internet there was an excellent description of cmForth and its meta compiler by Marc De Groot. It is often mentioned in discussions of small Forth systems and small meta compilers.
cmForth generates optimized native code for the Novix. A version was also ported to the Harris RTX 2000. Instead of a compiler that distinguishes between normal and IMMEDIATE words cmForth uses a compiler and an interpretter wordlist. It uses FOR NEXTs instead of DO LOOPs to simplify things. You can meta compile it from source on the PC and it can meta compile itself from source from a few lines of code. The meta compiler is simple because cmForth is simple and because the target machine and the target Forth system use the same assembler and compiler words as the meta compiler. Actually cmForth is the assembler since it is really a native code compiler.
Dr. C. H. Ting's book Footsteps in an Empty Valley began his More on Forth Engines newsletter series with information on cmForth and Novix. It is one of his products at Offete Enterprises Inc. It contains about fifty pages about the Novix NC4000 and another hundred pages about cmForth.
From chapter 3 in Footsteps in an Empty Valley, the cmForth Operating System:
"There are many important innovations in cmForth worth of your special attention. First is the optimizing compiler which takes normal Forth source code and compiles very short and efficient NC4000 machine instructions. Next is the dual threaded vocabulary structure in which all the compiler directives and smart compiling/assembling words are linked together, separate from the regluar FORTH vocabulary. The interpreter searches only the FORTH vocabulary. The compiler first searches the COMPILER vocabulary and then the FORTH vocabulary. This searching method eliminates the necessity of immediate words. Lastly, a very simple linking method is used to compile words into a target dictionary, which can later be isolated from the main dictionary and burned into EPROM. These innovations in time will make significant impact in the Forth community, leading to better and more efficient Forth systems and programs."
It gave a presentation on A Simple Meta Compiler to a local FIG chapter. This was a traditional but simple meta compiler. It used several wordlists on the host to hold the meta compiler, the target assembler, and the target wordlist (or actually host words with the target names that when executed compile target words into the target.) After I had a working target system P21Forth could now be made to compile a new copy of itself with a new meta compiler. I realized that this clone compiler could be really simple because everything was the simplest case. I only had to redesign a couple of the IMMEDIATE words in eForth so the eigth words that I needed to change all began with a literal containing the address of the word that they compiled.
I did another presentation for FIG about A One Word Meta Compiler and got some nice positive feedback. The heart of this clone compiler is a single word called META. This word transforms the normal host compiler into a meta compiler by modifying just a few of the host compiler IMMEDIATE words into meta compiling words.
We examined what the Forth word IF does earlier. In a normal Forth compiler this word is an IMMEDIATE word that executes during compiling and compiles code to execute the host word 0BRANCH (or its equivalent) into the host Forth system and leaves the address of the unresolved branch to be resolved later by an ELSE or a THEN.
In a meta compiler an IF must execute when meta compiling and compile into the target the code to execute the target 0BRANCH word and leave an address to be resolved later. In the case of this clone compiler the normal Forth IF can be transformed into a meta compiling IF by making one small change. It holds the address of the host 0BRANCH in a LITERAL it uses this to compile this into the host Forth. If it is pointed at a target Forth instead it will happily compile the host 0BRANCH into this target system. That would of course do no good since the target system couldn't execute it. But if the address of the target 0BRANCH is placed into the data field of the LITERAL at the start of the IF then the IF will compile the target 0BRANCH into the target system. It is as simple as that.
In this target system their are only 8 IMMEDIATE words that need to be transformed from normal compiling words into meta compiling words. These words are
:NONAME ; LITERAL IF UNTIL AGAIN ABORT" ."All of these words begin with a LITERAL that contains the address of a host primitive word used in compiling so they can all be transformed into meta compiling words by the same word.
: META ( -- ) ' ' 2 CELLS + ! ; \ as in META 0BRANCH IFThis word contains two TICKs. In the example above the first TICK returns the address of the first 0BRANCH found, and this will be the one in the target system. The second TICK returns the address of the first IF found, and this will be the one in the host meta compiler. The phrase META 0BRANCH IF must appear in the target source code before the first IF is encountered in the target code and after the target 0BRANCH is defined.
METAis first applied to the word ; right after the target primitive EXIT used by ; is defined. The word ; appears in the source code this Forth 138 times before the target ; is defined. This means that the first 138 times that ; appears in the target source code the target compiling ; will be used. After the target ; is defined it will be found first and it will be execute and it will do exactly what a normal Forth ; does.
The second word to be transformed with META is :NONAME. :NONAME in this version of Forth is used in the definition of : so :NONAME is the word to be transformed rather than :. In this direct threaded Forth colon definitions begin with a call to DO: so this is the address stored in the LITERAL field at the start of :NONAME. The word META is used to store the target DO: into this word to transform it into a meta compiling word. : is used 137 times in P21Forth before it is defined in the target. The first 137 times : is encountered in the target source the meta compiling : is executed and after that the target : will be executed.
The third word to be transformed is LITERAL. This word compiles a primitive called lit. META lit LITERAL is used to transform the normal Forth word LITERAL into a meta compiling one by substituting the address of the target lit. The word LITERAL appears 25 times in the target source before it is defined in the target. Until then the transformed meta compiling version will be executed.
The fourth word to be transformed is IF and we have covered that one above. IF is used 57 times in P21Forth before it is defined in the source.
The only other words needing to be transformed are UNTIL AGAIN ABORT" and ." and these words are used 10, 1, 3, and 3 times repsectively before they are defined in the source.
In this clone compiler the meta compiler executes a combination of normal Forth compiler code, meta compiler code, and target code. The target code dictionary is built and executed from a different address than the target compiler so both can be run. The target name dictionary is built at a different address but is linked into the metacompiler wordlist and after the compilation is complete the link between the two name lists is cut. Since the name dictionarys are treated as a single list the differences between this clone compiler and a normal Forth compiler are minimal.
This meta compiler is little more than a single word defined with only a few simple words. The word META is defined on one line, and invoked in eight other lines of the target source. Except for cutting the target system loose this is the full source:
: META ( -- ) ' ' 2 CELLS + ! ; \ as in META 0branch IF META EXIT ; \ ; used 138 times \ before it is defined in target META do: :NONAME \ : used 137 times META lit LITERAL \ LITERAL used 25 times META 0branch IF \ IF used 57 times META 0branch UNTIL \ UNTIL used 10 times META else AGAIN \ AGAIN used 1 time META abort" ABORT" \ ABORT" used 3 times META d" ." \ ." used 3 times
One might also argue that an ANS Forth meta compiler is a meta compiler that compiles an ANS compliant Forth system. These two things are not mutually exclusive. I think there is some justification for that position. However I for one would never suggest that the term an ANS Forth meta compiler should refer to a meta compiler that could compile any ANS Forth for any target on any host ANS Forth machine.